批量高效计算素数的算法

Question

<code=java>
import java.util.ArrayList;public class PrimeTest
{
/*
@param n 表示从1~n内求所有素数
*/
static void CalcPrime(int n)
{
boolean[] number=new boolean[n+1]; //废弃第0个,number为true的是素数，否则不是素数 //假设所有的数字都是素数
for(int i=1;i<number.length;i++)
{
   number[i]=true;
} /**
*算法解释：已知2是素数，那么所有2的倍数都不是素数。
*排除了所有2的倍数后，再对剩下不是2倍数的下一个数做排除。例如3，将3的倍数全部排除...再继续..
*/
for(int i=2;i<(number.length/2);i++)
{
if(number[i])
{
for(int j=i+i;j<number.length;j+=i)
{
number[j]=false;
}
}
} for(int i=2;i<number.length;i++)
{
if(number[i])
System.out.println(i);
}
} static void CalcPrime2(int n)
{
for(int i=2;i<n+1;i++)
{
boolean isPrime=true;
for(int j=2;j<Math.sqrt(i)+1;j++)
{
if(i%j==0)
{
  isPrime=false;
  break;
}
}
if(isPrime)
{
System.out.println(i);
}
}
} static void CalcPrime3(int n)
{
/**
*算法解释：将1-n的数字分成两拨，一拨是已知的素数表，一拨是未知的可能数
*例如：已知2，3为素数，那么4-n则为未知的素数可能。
*而判断素数的原则是拿可能数中的某个数去除素数表中的某个数，若发现素数表中没有数能整除它
*则它是一个新的素数
*/
ArrayList<Integer> arr=new ArrayList<Integer>();
arr.add(2);arr.add(3);
System.out.println(2+"\n"+3);
for(int i=4;i<n+1;i++)
{
boolean isPrime=true;
for(int j : arr)
{
   if(i%j==0)
   {
   isPrime=false;
   break;
   }
}
if(isPrime)
{
arr.add(i);
System.out.println(i);
}
}
} public static void main(String[] args) 
{
//Test
CalcPrime3(1000);
System.out.println("-------------------");
//CalcPrime2(1000);
//System.out.println("-------------------");
//CalcPrime3(1000);
}
}
</code>
第一种算法是批量求解素数的最快方法。
第二种算法速度相对慢，但是可用它来判断某个随机数字是否是素数。
第三种算法速度介乎中间位置，是对第二种算法的优化。
其中for(int j: arr)这段代码还可以优化

Answer 1

import java.io.*;
import java.util.ArrayList; 
import java.math.*;public class test
 {
public static void main(String[] args)
{
Integer[] flag = new Integer[10000];
Integer[] result = new Integer[10000];
int count = 0;
for (int i = 0; i < 10000; ++i) flag[i] = 1;
for (int i = 2; i < 10000; ++i) if (flag[i] == 1)
{
result[count++] = i;
for (int j = i*i; j < 10000; j+=i) flag[j] = 0;
}
System.out.println(count);
};
 }

Answer 2

把5楼的筛法求素数的算法整理一下：
import java.util.*;
public class test{
    public static void main(String[] args) {
        boolean[] flag = new boolean[10000];
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int i = 0; i < 10000; ++i){
          flag[i] = true;
        }
        
        for (int i = 2; i < 10000; ++i){
         if (flag[i]){
          result.add(i);
          for (int j = i*i; j < 10000; j+=i){
            flag[j] = false;
          }
         }
        }
        System.out.println(result);
        System.out.println("共有"+result.size()+"种结果");
    }
}

Answer 3

再整合一下:import java.util.*;
public class test{
    public static void main(String[] args) {
        boolean[] isNotPrime = new boolean[10000];
        ArrayList<Integer> result = new ArrayList<Integer>();
        
         for (int i = 2; i < 10000; ++i){
         if (!isNotPrime[i]){
          result.add(i);
          for (int j = i*i; j < 10000; j+=i){
            isNotPrime[j] = true;
          }
         }
        }
        System.out.println(result);
        System.out.println("共有"+result.size()+"种结果");
    }
}

Answer 4

呵,不会java,随便写的,编译了一下...

Answer 5

改成C，呵呵，乱写/**
 * 计算2~N的质数
 * skchen @ 2009-08-29 22:26
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define N 999999999main() {
    int i = 0;
    int *numbers;
    char *isNotPrime;
    int j = 0;
    int count = 0;
    numbers = malloc(N / 2);
    isNotPrime = malloc(N * sizeof(char));
    for (i = 0; i < N; i++) {
        isNotPrime[i] = 0;
        if (i < (N / 8)) {
            numbers[i] = 0;
        }
    }    for (i = 2; i < N; ++i) {
        if (isNotPrime[i] == 0) {
            numbers[count] = i;
            //printf("%d,", i);
            count++;
            for (j = i + i; j < N; j += i) {
                isNotPrime[j] = 1;
            }
        }
    }
    printf("总共%d个质数\n", count);
    printf("CPU运行时间:%d", clock());
    free(numbers);
    free(isNotPrime);
}