素數的篩法有很多種
在此給出常見的三種方法
以下給出的所有代碼均已認證這裡的測試
埃拉托斯特尼篩法
名字好長 :joy: 不過代碼很短
思路非常簡單，對于每一個素數，枚舉它的倍數，它的倍數一定不是素數
這樣一定可以保證每個素數都會被篩出來
還有，我們第一層循環枚舉到$\sqrt(n)$就好，因為如果目前枚舉的數大于n，那麼它能篩出來的數一定在之前就被枚舉過
比如說：
$\sqrt(100)=10$
不難發現我們從$20$枚舉所篩去的數一定被$5$篩過
1 #include<cstdio>
2 #include<cmath>
3 using namespace std;
4 const int MAXN=10000001;
5 inline int read()
6 {
7 char c=getchar();int f=1,x=0;
8 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
9 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
10 }
11 int vis[MAXN];
12 int n,m;
13 int main()
14 {
15 n=read();m=read();
16 vis[1]=1;//1不是質數
17 for(int i=2;i<=sqrt(n);i++)
18 for(int j=i*i;j<=n;j+=i)
19 vis[j]=1;
20 while(m--)
21 {
22 int p=read();
23 if(vis[p]==1) printf("No\n");
24 else printf("Yes\n");
25 }
26 return 0;
27 } 但是你會發現這份代碼隻能得30分
看來這種算法還是不夠優秀
下面我們來探索一下他的優化
另外，這種算法的時間複雜度：$O(n*logn)$
埃拉托斯特尼篩法優化版
根據唯一分解定理
每一個數都可以被分解成素數乘積的形式
那我們枚舉的時候，隻有在目前數是素數的情況下，才繼續枚舉就好
這樣可以保證每個素數都會被篩出來
1 #include<cstdio>
2 #include<cmath>
3 using namespace std;
4 const int MAXN=10000001;
5 inline int read()
6 {
7 char c=getchar();int f=1,x=0;
8 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
9 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
10 }
11 int vis[MAXN];
12 int n,m;
13 int main()
14 {
15 n=read();m=read();
16 vis[1]=1;//1不是質數
17 for(int i=2;i<=sqrt(n);i++)
18 if(vis[i]==0)
19 for(int j=i*i;j<=n;j+=i)
20 vis[j]=1;
21 while(m--)
22 {
23 int p=read();
24 if(vis[p]==1) printf("No\n");
25 else printf("Yes\n");
26 }
27 return 0;
28 } 
果然，加了優化之後這種算法快了不少
可以證明，它的複雜度為：$O(n*log^{logn})$
這種算法已經非常優秀了，但是對于1e7這種極端資料，還是有被卡的風險
那麼，還有沒有更快的篩法呢？
答案是肯定的！
歐拉篩
我們思考一下第二種篩法的運算過程
不難發現，對于6這個數，它被2篩了一次，又被3篩了一次
第二次篩顯然是多餘的，
我們考慮去掉這步運算
1 #include<cstdio>
2 #include<cmath>
3 using namespace std;
4 const int MAXN=10000001;
5 inline int read()
6 {
7 char c=getchar();int f=1,x=0;
8 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
9 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
10 }
11 int vis[MAXN],prime[MAXN];
12 int tot=0;
13 int n,m;
14 int Euler()
15 {
16 vis[1]=1;
17 for(int i=2;i<=n;i++)
18 {
19 if(vis[i]==0) prime[++tot]=i;
20 for(int j=1;j<=tot&&i*prime[j]<=n;j++)
21 {
22 vis[i*prime[j]]=1;
23 if(i%prime[j]==0) break;
24 }
25 }
26 }
27 int main()
28 {
29 n=read();m=read();
30 Euler();
31 for(int i=1;i<=m;i++)
32 {
33 int p=read();
34 if(vis[p]==1) printf("No\n");
35 else printf("Yes\n");
36 }
37 return 0;
38 } 對于這份代碼，我們分情況讨論
當$i$是素數的時候，那麼兩個素數的乘積一定沒有被篩過，可以避免重複篩
當$i$不是素數的時候
程式中有一句非常關鍵的話
if(i%prime[j]==0) break; 如果我們把$i$的唯一分解形式表示為$i = p_1^{a_1}p_2^{a_2} \dots p_n^{a_n}$
這句話可以保證：本次循環隻能篩除不大于${p_1}*i$的數
這樣的話每個數$i$都隻能篩除不大于$i$乘$i$的最小素因子的數
反過來，每個數隻能被它的最小素因子篩去。
也就可以保證每個數隻會被篩一次(這一步好像不是很顯然，我在最後會給出證明)
舉個例子，
設$i=2*3*5$，此時能篩去$i*2$，但是不能篩去$3*i$
因為如果能曬出$3*i$的話，
當$i_2=3*3*5$時，篩除$2*i_2$就和前面重複了
另外為了友善大家直覺了解，給出一張圖表
這樣顯得直覺一些
大家好好揣摩揣摩
上面的證明：我自己瞎yy的可能不是很嚴謹
現在我們需要證明$i = p_1^{a_1}p_2^{a_2} \dots p_n^{a_n}$隻會被$p_1$篩去
那麼我們需要證明三個條件
1.$i$一定被$p_1$和$p_1^{a_1 - 1}p_2^{a_2} \dots p_n^{a_n}$篩除過
很顯然，在枚舉到$p_1$之前不會有其他素因子使$p_1^{a_1 - 1}p_2^{a_2} \dots p_n^{a_n}$停止循環
2.$i$不會被$p_1^{a_1}p_2^{a_2 - 1} \dots p_n^{a_n}$篩去
同樣也很顯然，當枚舉到$p_1$時就會停止循環
可以看出這種算法的時間效率是非常高的！
時間複雜度：嚴格$O(n)$
總結
在一般情況下，第二種篩法已經完全夠用。
第三種篩法的優勢不僅僅在于速度快，而且還能夠篩積性函數，像歐拉函數，莫比烏斯函數等。
這個我以後還會講的
作者：自為風月馬前卒
個人部落格http://attack204.com//
出處：http://zwfymqz.cnblogs.com/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。