数论-求n以内的质数

一、埃拉托斯特尼筛法

　　名字很高大上，然而并没有什么卵用……

思路：

　　在把<=√n的质数所有的<=n的倍数剔除，剩下的就都是质数了，很容易理解……

　　复杂度O(nloglogn)

 1 #include<cmath>
 2 const int MAXN=;
 3 int b[MAXN/2],top;
 4 bool a[MAXN];
 5 void cal_prime_num(int n)
 6 {
 7     k=sqrt(n);
 8     for(int i=2;i<k;i++)
 9     {
10         if(!a[i])
11         {
12             int j=1;
13             b[++top]=i;                         
14             while(i*j<n)
15             {
16                    a[i*j]=true;
17                    ++j;
18             }
19         }
20      }
21 }

二、欧拉筛

　　上一个筛法似乎复杂度不大，但是遇到10⁷规模的数据就会炸，主要是因为一个数会被不同的质数筛好几遍，欧拉筛保证一个合数只被它的最小质因子筛去一遍，这就是整个代码最核心的部分，也是难理解的部分，然而只有一句话：

1 if(!i%pri[j])break;

　　证明转自他人博客：

prime数组中的素数是递增的，当 i 能整除 prime_j，那么 i*prime_j+1这个合数肯定被prime_j乘以某个数筛掉。
因为i中含有prime_j，prime_j比prime_j+1小。接下去的素数同理。所以不用筛下去了。
在满足i%prme_j==0这个条件之前以及第一次满足改条件时,prime_j必定是prime_j*i的最小因子。

　　复杂度O(n)

　　其余的代码就很容易理解了：

 1 #include<cmath>
 2 const int MAXN=;
 3 int b[MAXN/2],top;
 4 bool ispri[MAXN];
 5 void cal_prime_num(int n)
 6 {
 7     for(int i=2;i<=n;++i)
 8     {
 9         if(!ispri[i])pri[++top]=i;
10         for(int j=1;j<=top&&i*pri[j]<=n;++j)
11         {
12             ispri[i*pri[j]]=true;
13             if(!i%pri[j])break;
14         }
15     }
16 }