首页 > > 程序设计 > C/C++ >

[算法]浅谈求n范围以内的质数（素数）

2018-11-28 08:50:48来源：博客园阅读 ()

汗颜，数学符号表达今天才学会呀-_-#

下面是百度百科对质数的定义

质数（prime number）又称素数，有无限个。

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

求质数的方法自然不少，但主要还是有三大方法，它们运用在不同的领域，根据数据也会变化；

1、傻子求质数法

这种方法十分无脑，任何一个人都能想出来，但这种方法竟然还有几个优化ORZ

时间复杂度是O($N^{2}$);

1.1、无优化版本

 1 void prime()
 2 {
 3     int N = 10000;
 4     int primes[N],pos=0;
 5     register int i,j;
 6     for(i=2;i<N;i++){
 7         bool Flag=0;
 8         for(j=2;j<i;j++)
 9             if(i%j==0)Flag=1;
10         if(Flag==0)primes[++pos]=i; 
11     }
12 }

这也是所有求质数中最朴素的求法，自然在平常当中不会使用。

然而有些奇葩题目，求质数的次数很少，就可以用这个啦。↖(^ω^)↗

证明：质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数 ——百度百科。

1.2、n/2 优化版本

 1 void prime()
 2 {
 3     int N = 10000;
 4     int primes[N],pos=0;
 5     register int i,j;
 6     for(i=2;i<N;i++){
 7         bool Flag=0;
 8         for(j=2;j<=i/2;j++)
 9             if(i%j==0)Flag=1;
10         if(Flag==0)primes[++pos]=i; 
11     }
12 }

这种优化就比上一种快一倍（时间复杂度），但仍然有缺陷，能不能再快一点？?_?

证明：x/2以上的数增加就会重复。

1.3、n开平方优化版本

 1 void prime()
 2 {
 3     int N = 10000;
 4     int primes[N],pos=0;
 5     register int i,j;
 6     for(i=2;i<N;i++){
 7         bool Flag=0;
 8         for(j=2;j<=sqrt(n);j++)
 9             if(i%j==0)Flag=1;
10         if(Flag==0)primes[++pos]=i; 
11     }
12 }

这个就是傻子求法的最终版本了，时间复杂度已经优化到了极限（个人认为）。囧rz

证明：因为x=$\sqrt{N}^{2}$的平方，所以sqrt(x)以上的数增加就会重复。

2、埃氏（Eratosthenes）筛法

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。——百度百科

这种筛法大概是我初一学了快一个学期，开始学质因数时，自己过不了找质数一个题，然后接触的一个算法。

埃氏的筛法思想精华，主要是把质数的倍数剔除，剩下的那些就是质数。+_+

这种算法的时间复杂度是O(nloglogn)。

 1 void prime()
 2 {
 3     int N=10000;
 4     register int i,j;
 5     bool prim[N];
 6     memset(prim,0,sizeof(prim));
 7     prim[1]=1;
 8     for(i=2;i<=sqrt(N);i++)
 9         if(prim[i]==0) 
10             for(j=i+i;j<=N;j+=i)
11             prim[j]=1;
12 }

3、欧拉（Euler）筛选法

欧拉筛法就是所谓中的高级筛法，时间复杂度削减到了O($N^{2}$)。

它的思想是在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

 1 void prime()
 2 {
 3     int N=10000;
 4     int prim[N],bz[N],top=0;
 5     memset(bz,0,sizeof(bz));
 6     register int i,j;
 7     for(i=2;i<=N;i++){
 8         if(!bz[i])prim[++top]=i;
 9          for(j=0;j<=top&&i*prim[j]<=N;j++){
10                  bz[i*prim[j]]=1;
11                  if(i%prim[j]==0)break;
12           }
13     }
14 }