求素数的几种算法

1、根据质数的定义求 　　质数定义：只能被1或者自身整除的自然数（不包括1），称为质数。 　　利用它的定义可以循环判断该数除以比它小的每个自然数（大于1），如果有能被它整除的，则它就不是质数。 对应代码是： void printPrime(int n){//判断n是否是质数 boolean isPrime=true;//是否是质数的标志 for(int i=n-1;i>1;i—){//n除以每个比n小比1大的自然数 if(n%i==0){//如果有能被整除的，则不是质数 isPrime=false; } } if(isPrime){//如果是质数，则打印出来 System.out.print(n+" "); primeNumber++;//记录质数的个数 if(primeNumber==0)//输出10个质数后换行 System.out.println(); } } 2、利用一个定理——如果一个数是合数，那么它的最小质因数肯定小于等于他的平方根。例如：50，最小质因数是2，2<50的开根号 再比如：15，最小质因数是3，3<15的开根号 　　合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数，则它是质数。 　　上面的定理是说，如果一个数能被它的最小质因数整除的话，那它肯定是合数，即不是质数。所以判断一个数是否是质数，只需判断它是否能被小于它开跟后后的所有数整除，这样做的运算就会少了很多，因此效率也高了很多。 对应代码是： void printPrime(int n){//判断n是否是质数 boolean isPrime=true;//是否是质数的标志 int s=(int)Math.sqrt(n);//对n开根号 for(int i=s;i>1;i—){//n除以每个比n开根号小比1大的自然数 if(n%i==0){//如果有能被整除的，则不是质数 isPrime=false; } } if(isPrime){//如果是质数，则打印出来 System.out.print(n+" "); primeNumber++;//记录质数的个数 if(primeNumber==0)//输出10个质数后换行 System.out.println(); } } 3、筛法求质数，效率最高，但会比较浪费内存 　　首先建立一个boolean类型的数组，用来存储你要判断某个范围内自然数中的质数，例如，你要输出小于200的质数，你需要建立一个大小为201（建立201个存储位置是为了让数组位置与其大小相同）的boolean数组，初始化为true。 　　其次用第二种方法求的第一个质数（在此是2），然后将是2的倍数的数全置为false（2除外），即2、4、6、8……位置上置为false。然后是3的倍数的全置为false（3除外），一直到14（14是200的开平方），这样的话把不是质数的位置上置为false了，剩下的全是质数了，挑着是true的打印出来就行了。 对应代码是： boolean[] printPrime(int range){ boolean[] isPrime=new boolean[range+1]; isPrime[1]=false;//1不是质数 Arrays.fill(isPrime, 2,range+1,true);//全置为true（大于等于2的位置上） int n=(int)Math.sqrt(range);//对range开根号 for(int i=2;i<=n;i++)//注意需要小于等于n if(isPrime[i])//查看是不是已经置false过了 for(int j=i;j*i<range;j++)//将是i倍数的位置置为false isPrime[j*i]=false; return isPrime;//返回一个boolean数组 } 4、计算n以内的素数存在数组，可以计算n*n以内的素数个数 //计算1000*1000以内的素数个数 #include<stdio.h> #include<math.h> #include<time.h> int a[168]= {2}; void init(void) //求出1000以内的所有素数,储存在数组中 { int i,j,k=1,sure=1; for(j=3; j<1000; j++) { for(i=2; i<=sqrt(j); i++) if(j%i==0) { sure=0; break; } if(sure) a[k++]=j; sure=1; } /* for(i=0;i<168;i++) printf("]",a[i]); */ } int prime(long n) //判断该数是否为素数 { int i; if(n<2) return 0; if(n==2) return 1; for(i=0; i<168; i++) { if(n%a[i]==0) return 0; if(a[i]>sqrt(n)) break; } return 1; } void main(){ long n,i; clock_t start,over; int sum; while(scanf("%ld",&n)) { start=clock(); init(); sum=1; for(i=3; i<=n; i+=2) if(prime(i)) sum++; printf("%d\n",sum); over=clock(); printf("消耗时间:%lfms\n",(double)(over-start)); } return 0; } 此外，还有 Monte carlo蒙特卡罗算法、伪素数算法、拉宾米勒算法。 参考文章： 求质数的几种算法  求素数最优算法