作為和數學高度結合的一門學科，程式設計中經常會用到數學上的性質和概念，或者說，計算機一開始就是為了解決數學問題而發明的。在做題的過程中，我們經常遇到質數相關的題目，那麼，我們如何判斷一個數是不是質數呢？如何把質數全部打入表中呢？今天，我將介紹三種常見的篩取質數的方法。
int main()
{
int n, c, N = 0, prime[10000];//質數陣列
scanf("%d", &n);
for (int i = 2; i <= n; i++)//檢測i是否為質數
{
c = 1;
for (int j = 2; j * j <= i + 1; j++)//測試i是否能被j整除
if (i % j == 0 && i != 2)
{
c = 0;
break;
}
if(c) prime[N++] = i;//填入並計數
}
for (int i = 0; i < N; i++) printf("%d ", prime[i]);
return 0;
}
根據質數的定義，質數有且只有兩個因數，即1和它本身。
樸素篩就根據這最基本的性質，從2開始遍歷，直到它的平方根，依次取餘，如果整除了就違反了質數有且只有兩個因數的性質，可以將其排除。
之所以只需要遍歷到平方根，是因為整除時，結果也是它的一個因數，故只需要遍歷到平方根，便可以將所有可能是因數的數試到。
for (int i = 2; i <= n; i++)//檢測i是否為質數
{
c = 1;
for (int j = 2; j * j <= i; j++)//測試i是否能被j整除
if (i % j == 0 && i != 2)
{
c = 0;
break;
}
if(c) prime[N++] = i;//填入並計數
}
這裡是樸素篩的核心部分。
值得注意的是，for迴圈的跳出條件設定為j*j<=i，避免了sqrt函數的使用，可以顯著提升執行速度。
而變數c的設定則是為了標識i是否是質數，若是因為判斷為合數而跳出，則將c賦為0，後續不做處理，反之，將其存入陣列。
整個演演算法的時間複雜度為O(nlogn)。很顯然，這個演演算法是最基礎的暴力遍歷，如果題目給的資料大一點就會被T得很慘，比賽時間充裕的情況儘量不要用樸素篩，就跟儘量用快排別用冒泡一個道理。
#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定義最大值
bool priNum[maxNum];//質數為真，否則為假
void savePriNum()//建立預處理質數集
{
for (int i = 0; i < maxNum; i++)
priNum[i] = true;//預設真
priNum[0] =priNum[1] = false;
for (int i = 2; i * i < maxNum ; i++)//依次篩掉i的倍數，不包括i
for (int j = 2 * i; j < maxNum; j += i)
priNum[j] = false;
}
int main()
{
savePriNum();
int n;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
if (priNum[i])
printf("%d\n", i);
return 0;
}
質數有且只有兩個因數，那也就是說，任何數的倍數都不可能是質數，那我們只需要在遍歷2到它的平方根，並標記這些數在要求範圍內的倍數為合數，那剩下的數就是質數了。
#include<stdbool.h>
#define maxNum 1000000001//定義最大值
bool priNum[maxNum];//質數為真，否則為假
首先，我們先建立一個布林型陣列來存放質數。因為資料範圍極大，而我們只需要存放0和1來標記質數合數，所以我們採用值只有true和false的布林型變數，來節省空間。
void savePriNum()//建立預處理質數集
{
for (int i = 0; i < maxNum; i++)
priNum[i] = true;//預設真
priNum[0] =priNum[1] = false;
for (int i = 2; i * i < maxNum ; i++)//依次篩掉i的倍數，不包括i
for (int j = 2 * i; j < maxNum; j += i)
priNum[j] = false;
}
我們將存表操作封裝進函數中。
首先，我們預設每個數都為質數，接著，特判0和1不是質數，同時，0和1也不在我們遍歷的過程中。
我們從2開始，遍歷到範圍最大值的平方根，標記這些數在要求範圍內的倍數為合數。
這樣，我們想判斷x是不是質數，只需要查詢priNum[x]的值就可以了。
整個演演算法的時間複雜度為O(nloglogn)，已經很逼近線性時間O(n)了，但是我們可以發現，埃氏篩在標記合數時，是有重複標記的。當一個合數擁有多個因數時，就會被標記多次，例如12擁有因數1，2，3，4，6，12，除去1和12，在遍歷2，3，4，6時，12都被標記了一次，所以，埃氏篩還並不是線性時間。
#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定義最大值
bool priNum[maxNum];//質數為真，否則為假
int pri[maxNum], N = 0;
void savePriNum()//建立預處理質數集
{
for (int i = 0; i < maxNum; i++)
priNum[i] = true;//全部填入真
priNum[0] = priNum[1] = false;
for (int i = 2; i * i <= maxNum; i++)
if (priNum[i])
{
pri[N] = i;//存入陣列並計數
N++;
for (int j = 0; j < N; j++)//若i為質數，則標記它和其他質數的每一個乘積
if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;
else break;//
}
else
for (int j = 0; j < N; j++)
{
if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;//若i為合數，則標記它和其他質數的乘積
if (i % pri[j] == 0) break;//直到i整除到某質數
}
return 0;
}
int main()
{
savePriNum();
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
if (priNum[i])
printf("%d ", i);
return 0;
}
尤拉篩又稱線性篩，在尤拉篩中每個合數都只會被標記一次，因此，演演算法的時間是線性的，時間複雜度到了O(n)。
為了實現每個合數只被標記一次，在尤拉篩中我們規定每個合數都只會被它的最小因數標記，這裡的意思是通過該數最小因數*某數=該數來標記該數。
#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定義最大值
bool priNum[maxNum];//質數為真，否則為假
int pri[maxNum], N = 0;
預處理時，我們另外建立一個陣列，用於即時存放篩選出的質數，同時設定變數N用於記錄當前質數數量。
void savePriNum()//建立預處理質數集
{
for (int i = 0; i < maxNum; i++)
priNum[i] = true;//全部填入真
priNum[0] = priNum[1] = false;
for (int i = 2; i * i <= maxNum; i++)
;//......
return 0;
}
我們同樣將存表操作封裝進函數中，預設存真，特判01，同樣的遍歷至平方根，不做贅述。
if (priNum[i])
{
pri[N] = i;//存入陣列並計數
N++;
for (int j = 0; j < N; j++)//若i為質數，則標記它和其他質數的每一個乘積
if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;
else break;//
}
當我們遍歷到一個質數時，我們將其存入質數陣列並計數，然後將其與已經存入的質數相乘，並標記相乘的積為合數。
兩個不同質數相乘的積有且只有4個因數，兩個相同質數相乘的積有且只有3個因數，這是分解質因數的原理。
也因此，我們通過此法標記的數，必然是通過它的最小因數來標記的。
else
for (int j = 0; j < N; j++)
{
if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;//若i為合數，則標記它和其他質數的乘積
if (i % pri[j] == 0) break;//直到i整除到某質數
}
而當我們遍歷到一個合數時，我們同樣將其與已經存入的質數相乘，並標記相乘的積為合數。
但尤拉篩的精髓之處來了。
當該數在相乘中遍歷到自己的一個因數後，就需要break跳出，終止迴圈。
同樣以12舉例，當i遍歷到4，j遍歷到2時，4%2==0，此時需要跳出，j不能繼續遍歷到3，若通過4*3=12來標記12，在i遍歷到6時，6*2=12便會重複遍歷，也違反了合數需要被自己的最小因子標記的規則。
樸素篩和埃氏篩的實現原理是比較簡單的，使用的場景也比較廣泛，但在個別的競賽題中會T，必須使用尤拉篩。
尤拉篩理解的過程是有點難的，但在真正理解之後思路會非常清晰，主要就是合數需要被自己的最小因子標記的規則，需要細細體會。
以上便是質數篩三種篩法的介紹，本文由涼茶coltea撰寫，轉載請註明出處。