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 }