想要快速地篩出一定上限內的素數？

下面這種方法可以保證范圍內的每個合數都被刪掉（在 bool 數組裡面標記為非素數），而且任一合數只被：

“最小質因數 × 最大因數（非自己） = 這個合數”

的途徑刪掉。由於每個數只被篩一次，時間復雜度為 O(n)。

歐拉篩

先浏覽如何實現再講其中的原理。

實現

#include <cstdio>
#include <cstring>
bool isPrime[100000010];
//isPrime[i] == 1表示：i是素數
int Prime[6000010], cnt = 0;
//Prime存質數
void GetPrime(int n)//篩到n
{

memset(isPrime, 1, sizeof(isPrime));
//以“每個數都是素數”為初始狀態，逐個刪去
isPrime[1] = 0;//1不是素數
for(int i = 2; i <= n; i++)
{

if(isPrime[i])//沒篩掉 
Prime[++cnt] = i; //i成為下一個素數
for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++)
{

//從Prime[1]，即最小質數2開始，逐個枚舉已知的質數，並期望Prime[j]是(i*Prime[j])的最小質因數
//當然，i肯定比Prime[j]大，因為Prime[j]是在i之前得出的
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0)//i中也含有Prime[j]這個因子
break; //重要步驟。見原理
}
}
}
int main()
{

int n, q;
scanf("%d %d", &n, &q);
GetPrime(n);
while (q--)
{

int k;
scanf("%d", &k);
printf("%d\n", Prime[k]);
}
return 0;
}

import time
def get_prime(x):
for i in range(2,x+1):
if st[i]:
primes.append(i)
for j in range(len(primes)):
if primes[j]*i>x:
break
st[primes[j]*i]=False
if i%primes[j]==0:
break
start=time.time()
n=10000
N=n+5
st=[True]*N
primes=[]
get_prime(n)
print(len(primes))
end=time.time()
print('程序運行時間',end-start)
with open('./primes.txt','w') as f:
f.write('\n'.join(map(str,primes)))

原理概述

代碼中，外層枚舉i=1→n。對於一個 ii，經過前面的腥風血雨，如果它還沒有被篩掉，就加到質數數組 Prime[]中。下一步，是用 i來篩掉一波數。

內層從小到大枚舉 Prime[j]。i×Prime[j] 是嘗試篩掉的某個合數，其中，我們期望 Prime[j] 是這個合數的最小質因數 (這是線性復雜度的條件，下面叫做“篩條件”)。它是怎麼得到保證的？

j 的循環中，有一句就做到了這一點：

if(i % Prime[j] == 0)
break;

j 循環到 i \mod Prime[j] == 0imodPrime[j]==0 就恰好需要停止的理由是：

下面用 s(smaller) 表示小於 j 的數，L(larger)表示大於 j 的數。

① i 的最小質因數肯定是 Prime[j]。

（如果 i 的最小質因數是 Prime[s] ，那麼 Prime[s] 更早被枚舉到（因為我們從小到大枚舉質數），當時就要break）

既然 ii 的最小質因數是 Prime[j]，那麼 i×Prime[j] 的最小質因數也是 Prime[j]。所以，j 本身是符合“篩條件”的。

②i×Prime[s] 的最小質因數確實是 Prime[s]。

（如果是它的最小質因數是更小的質數 Prime[t]，那麼當然Prime[t] 更早被枚舉到，當時就要break）

這說明 j 之前（用 i×Prime[s] 的方式去篩合數，使用的是最小質因數）都符合“篩條件”。

③ i × Prime[L] 的最小質因數一定是 Prime[j]。

（因為 i 的最小質因數是 Prime[j]，所以 i×Prime[L] 也含有 Prime[j] 這個因數（這是 i 的功勞），所以其最小質因數也是 Prime[j]（新的質因數 Prime[L] 太大了））

這說明，如果 j 繼續遞增（將以 i×Prime[L] 的方式去篩合數，沒有使用最小質因數），是不符合“篩條件”的。

小提示：

當 ii 還不大的時候，可能會一層內就篩去大量合數，看上去耗時比較大，但是由於保證了篩去的合數日後將不會再被篩（總共只篩一次），復雜度是線性的。到 ii 接近 nn 時，每層幾乎都不用做什麼事。