樸素篩法：

#include #include using namespace std;const int N=1000010;int primes[N],cnt;bool st[N];void get_primes(int  n){        for(int i=2;i<=n;i++){                 if(!st[i])//st==0 代表的是這個數是質數        {            primes[cnt++]=i;        }        for(int j=i+i;j<=n;j+=i)        {            st[j]=true;        }    }    }int main(){    int n;    cin>>n;    get_primes(n);        cout<
這個樸素算法的思路就是，枚舉這些數，首先在st數組初始化時，就是已經把這個數組內的值都初始化為0，也就是說都是看成是質數。。。。

(相關資料圖)
然后，如果這個數確實是質數，那么我們就可以把這個數放入我們存質數的數組里面去，然后對質數的個數進行增加，并且，我們把這個質數的倍數（2倍，3倍，4倍。。。。。。）的st都標記為合數（st=1），范圍是這個數小于n。。
但是我我們舉個例子就可以發現這個樸素的算法有明顯的可以優化的地方
讓我們看這個代碼段
for(int i=2;i<=n;i++){ for(int j=i+i;j<=n;j+=i)        {            st[j]=true;        }}
假如這個n是等于12
i=2  倍數有2,4,6,8,10,12 (都會被篩)
i=3  倍數有3，6，9，12(都會被篩)
i=4  倍數有4，8，12 (都會被篩)
............
從這個中間我們可以看到4，6，8和12是多次被賦值為true的，這個方就會降低算法的效率。。。。這個地方我們就要想辦法優化。。。。。
就有一種想法就是：我們不要把所有數的倍數都進行一個賦值，而是有一部分的數進行倍數的賦值------這個數就是質數
也就是說我們對質數的倍數進行賦值----也就是一個埃及人發明的。。---------我們稱之為埃式篩法
代碼如下：
也就把這個代碼段放入循環中：
#include #include using namespace std;const int N=1000010;int primes[N],cnt;bool st[N];void get_primes(int  n){        for(int i=2;i<=n;i++){                 if(!st[i])//st==0 代表的是這個數是質數        {            primes[cnt++]=i;//。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。                for(int j=i+i;j<=n;j+=i)        {            st[j]=true;// 這個是被放進來的部分}//。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。        }        }    }int main(){    int n;    cin>>n;    get_primes(n);        cout<
在上面的埃式篩法中，我們做到了一個優化，但是這個優化也不是很完全：
還是舉這個例子來說，n=12時
i=2  倍數有2,4,6,8,10,12 (都會被篩)
i=3  倍數有3，6，9，12 (都會被篩)
i=4  倍數有4，8，12   但是根據算法的思路，我們可以知道，4不是質數所以他的倍數不會被篩，就是這種地方優化了算法的效率。。
然后就是線性篩法，比埃式篩法更快，原因是：做到了每一個數都只被篩一遍-----也就是每一個數只會被他的最小的質因子去篩掉（核心）。
#include #include using namespace std;const int N=1000010;int primes[N],cnt;bool st[N];void get_primes(int  n){        for(int i=2;i<=n;i++){//外層循環是枚舉所有的數的       if(!st[i]) primes[cnt++]=i;     for(int j=0;primes[j]<=n/i;j++)     //j是從小到大枚舉所有的質數           {         st[primes[j]*i]=true;         if(i%primes[j]==0) break;     }}}int main(){    int n;    cin>>n;    get_primes(n);        cout<
........................................................................................................
引用：(這個地方是沒看懂他怎么想的，但是這個例子部分還是很明顯易懂的)
②歐拉篩法：任何一個合數都可以寫成幾個質數相乘的形式，也就是任何一個合數至少有一個最小質因子，而每一個質數的倍數一定不是質數，所以我們可以通過每一個合數的一個最小素因子去篩掉它，并且只篩掉一次，這樣就把時間復雜度降到了O(n)。其中就是這條語句起著至關重要的作用：if(i%prime[j]==0)break;為什么呢？舉個栗子：假設當前i=9，prime素數表里有2，3，5，7，即先篩掉2*9=18，然后篩掉3*9=27，判斷9%3==0，退出當前循環。因為9=3*3，如果繼續篩掉5*9，相當于篩3*3*5=3*15，而這個數在i=15時篩掉就可以了。因此，可以用以下的推導證明上面的結論：假設pi是當前i的最小質因子，那么素數表有p1i+1<...，枚舉當前質數表p[j]，j從小到大枚舉，直到i%p[j]==0這個條件時，前面所有質數p[j]都是i*p[j]的最小質因子，如果繼續枚舉下去，即下一個要被篩掉的合數為i*prime[j+1]，因為i中已經含有一個最小質因子prime[j]，設i=k*prime[j]，則i*prime[j+1]=k*prime[j]*prime[j+1]=k"*prime[j]，顯然k">i，k"*prime[j]可以留在后面被篩掉。換句話說，prime[j+1]已不是i*prime[j+1]的最小質因子，i*prime[j+1]必然可以被一個更小的質數prime[j]篩掉，那么k"=i*prime[j+1]/prime[j]=k*prime[j+1]就一定比i大，即下一次i遍歷到i=k"時，k"*prime[j]卻被其最小素因子prime[j]篩掉，而不是prime[j+1]，這就相當于再篩選了一次（增加了時間復雜度），所以只需將j遍歷到i的最小素因子prime[j]就可以了，即保證每一個合數只被其最小質因子篩掉，這樣把時間復雜度完美地從O(nloglogn)降到了O(n)。
................................................................................................................
根據自己的分析：
我們用每個合數的最小質因子來進行篩選之所以被稱為線性，是因為： 1-n之內的任何一個合數一定會被篩掉,而且篩的時候只用最小質因子來篩,
每一個數都只有一個最小質因子,所以每個數都只會被篩一次,因此線性篩法是線性的。
具體的步驟就是：之前每篩到一個素數j，就將這個素數放入到primes[]中，在每次循環中，從頭開始遍歷primes[],篩選出的合數就是primes[j]*i,
為了保證每個數只被篩選一次，就要保證每個合數都是被其最小的質因子篩選掉的，所以我們就要找到primes【j】*i的最小質因子，所以我們需分情況討論：
首先我們知道，primes【j】*i 的最小質因子應該是min（primes【j】,i的最小質因子），也就是說我們需要找到二者中的最小值。。。。。
1.當i%primes[j]不等于0時
此時primes[j]小于i的所有質因子，因為primes[j]是從小到大進行枚舉的，如果primes[j]是i中質因子之一，那么就會滿足i%primes[j]等于0。
所以我們就可以知道了i的質因子還在后面，還沒有加入到我們的primes數組中，所以也就是說，primes【j】就是i*primes【j】的最小質因子
------------所以這種情況下，primes[j]是可以用來篩這個合數 primes【j】*i 的。。。。
2.當i%primes[j]等于0時
說明此時，primes【j】就是i的最小質因子，原因就是：primes[j]是從小到大進行枚舉的，這個時候，很明顯我們就可以知道primes【j】就是i*primes【j】的最小質因子
綜合以上的情況我們就可以知道用這個primes[j]是可以用來篩這個合數 primes【j】*i 是合理的，因為在這兩種情況下，primes【j】就是i*primes【j】的最小質因子。。。。
如何保證這個數只被篩一次，也就是說我們里面這個內循環，每次只能篩一個數走，也就是說，只有一個地方會被設置為true每一次。
所以一旦這個primes里的質數篩走一個數之后就要內循環break，這個時候我們就需要找到這個break的條件。。。
循環應該在i % primes[ ] == 0時停止。。。。。
在一些測試的數據上，如果n<1e6,線性篩和埃式篩的時間效率差不多，如果n>1e7的時候，線性比埃式要快了一倍左右。。。。
1e6:
1e7:
線性篩法是對樸素篩法的進一步優化，埃式篩法的缺陷在于，對于同一個合數，可能被篩選多次。為了確保每一個合數只被篩選一次，我們用每個合數的最小質因子來進行篩選之所以被稱為線性，是因為： 11~ n?之內的任何一個合數一定會被篩掉,而且篩的時候只用最小質因子來篩,每一個數都只有一個最小質因子,所以每個數都只會被篩一次,因此線性篩法是線性的.具體操作方法為：之前每篩到一個素數，便將這個素數放入到primes[ ]中，在每次循環中，從頭開始遍歷primes[ ]， 篩選出的合數為 primes[j]×i??????[?]×?為了保證每個數只被篩選一次，就要保證每個合數都是被其最小質因子篩選掉的，即要找出 primes[j]×i??????[?]×?的最小質因子，所以我們分兩種情況討論：首先說明：primes[j]×i??????[?]×?的最小質因子應該是 min(???(primes[j]??????[?]， i?的最小質因子），即二者中的最小值1.當 i?% primes[j]≠0??????[?]≠0時說明此時 primes[j]??????[?]小于 i?的所有質因子，因為 primes[j]??????[?]是從小到大進行枚舉的，如果 primes[j]??????[?]是 i?的質因子之一，那么應該滿足 i?% primes[j]=0??????[?]=0才對。所以此時 primes[j]??????[?]是 primes[j]×i??????[?]×?的最小質因子2.當 i?% primes[j]=0??????[?]=0時說明此時 primes[j]??????[?]是 i?的最小質因子（因為 primes[j]??????[?]是從小到大進行枚舉的），所以此時primes[j]??????[?]也是 primes[j]×i??????[?]×?的最小質因子綜上，使用 primes[j]??????[?]來篩選 primes[j]×i??????[?]×?是可行的，因為兩種情況下 primes[j]??????[?]都是 primes[j]×i??????[?]×?的最小質因子那么如何保證每個數都只被篩選一次？即循環應該在何時結束？循環應該在i % primes[ ] == 0的時候中止，理由如下：當 i?% primes[j]=0??????[?]=0的時候如果不中止，那么將進入下一次循環，下一次循環要篩掉的數字是 primes[j+1]×i??????[?+1]×?。對于 primes[j+1]×i??????[?+1]×?，i?的值沒有變，和上一步滿足 i?% primes[j]=0??????[?]=0時的 i?是一樣的，所以當前 i?的最小質因子仍為 primes[j]??????[?]；但是當前為 primes[j+1]??????[?+1]，即比上一次循環的 primes[j]??????[?]要大，那么此時 primes[j+1]??????[?+1]和 i?的最小質因子 (primes[j])(??????[?])相比，較小值為 i?的最小質因子 (primes[j])(??????[?])，所以 primes[j+1]×i??????[?+1]×?的最小質因子應該為 (primes[j])(??????[?])，那么 primes[j+1]×i??????[?+1]×?這個數應該由 (primes[j])(??????[?])來篩選掉，但是當前卻是由 (primes[j+1])(??????[?+1])篩選掉的，所以出現了重復篩選。因此，為了保證所有數只被篩選一次，循環需要在 i % primes[ ] == 0的時候中止若 n<106?<106，線性篩和埃氏篩的時間效率差不多; 若 n>107?>107,線性篩會比埃氏篩快了大概一倍作者：GodLan鏈接：https://www.acwing.com/activity/content/code/content/5374176/來源：AcWing著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。  
 關鍵詞：