線性篩，復(fù)雜度為O(n)蚜枢。與埃氏篩相比竟块，不會對已經(jīng)被標(biāo)記過的合數(shù)再進行重復(fù)標(biāo)記壶运，故效率更高。歐拉篩將合數(shù)分解為 (最小質(zhì)因數(shù) * 一個合數(shù)) 的形式浪秘，通過最小質(zhì)因數(shù)來判斷當(dāng)前合數(shù)是否已經(jīng)被標(biāo)記過蒋情。
const int maxn = 101; // 表長
int prime[maxn], pNum = 0; // prime記錄素數(shù)埠况，pNum記錄素數(shù)個數(shù)
bool p[maxn] = {false}; // p記錄當(dāng)前數(shù)是否被篩去
void eulerSieve(int n) // 查找記錄2-n的素數(shù)
{
for (int i = 2; i <= n; i++)
{
if (p[i] == false) // 如果未被篩過，則為素數(shù)
prime[pNum++] = i;
for (j = 0; j < pNum; j++)
{
if (i * prime[j] > n) // 當(dāng)要標(biāo)記的合數(shù)超出范圍時跳出
break;
p[i * prime[j]] = true; // 將已經(jīng)記錄的素數(shù)的倍數(shù)進行標(biāo)記
if (i % prime[j] == 0) //關(guān)鍵步驟
break;
}
}
}
歐拉篩的難點就在于對if (i % prime[j] == 0)這步的理解棵癣，當(dāng)i是prime[j]的整數(shù)倍時辕翰，記 m = i / prime[j]，那么 i * prime[j+1] 就可以變?yōu)?(m * prime[j+1]) * prime[j]狈谊，這說明 i * prime[j+1] 是 prime[j] 的整數(shù)倍喜命，不需要再進行標(biāo)記(在之后會被 prime[j] * 某個數(shù) 標(biāo)記)，對于 prime[j+2] 及之后的素數(shù)同理河劝，直接跳出循環(huán)壁榕，這樣就避免了重復(fù)標(biāo)記。
