讀完本文嚎货，你可以去力扣拿下如下題目：
-----------
素?cái)?shù)的定義看起來很簡單，如果一個(gè)數(shù)如果只能被 1 和它本身整除梅鹦，那么這個(gè)數(shù)就是素?cái)?shù)突颊。
不要覺得素?cái)?shù)的定義簡單鲁豪，恐怕沒多少人真的能把素?cái)?shù)相關(guān)的算法寫得高效。比如讓你寫這樣一個(gè)函數(shù)：
// 返回區(qū)間 [2, n) 中有幾個(gè)素?cái)?shù)
int countPrimes(int n)
// 比如 countPrimes(10) 返回 4
// 因?yàn)?2,3,5,7 是素?cái)?shù)
你會(huì)如何寫這個(gè)函數(shù)律秃？我想大家應(yīng)該會(huì)這樣寫：
int countPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim(i)) count++;
return count;
}
// 判斷整數(shù) n 是否是素?cái)?shù)
boolean isPrime(int n) {
for (int i = 2; i < n; i++)
if (n % i == 0)
// 有其他整除因子
return false;
return true;
}
這樣寫的話時(shí)間復(fù)雜度 O(n^2)爬橡，問題很大。首先你用 isPrime 函數(shù)來輔助的思路就不夠高效友绝；而且就算你要用 isPrime 函數(shù)，這樣寫算法也是存在計(jì)算冗余的肝劲。
先來簡單說下如果你要判斷一個(gè)數(shù)是不是素?cái)?shù)迁客，應(yīng)該如何寫算法。只需稍微修改一下上面的 isPrim 代碼中的 for 循環(huán)條件：
boolean isPrime(int n) {
for (int i = 2; i * i <= n; i++)
...
}
換句話說辞槐，i 不需要遍歷到 n掷漱，而只需要到 sqrt(n) 即可。為什么呢榄檬，我們舉個(gè)例子卜范，假設(shè) n = 12。
12 = 2 × 6
12 = 3 × 4
12 = sqrt(12) × sqrt(12)
12 = 4 × 3
12 = 6 × 2
可以看到鹿榜，后兩個(gè)乘積就是前面兩個(gè)反過來海雪，反轉(zhuǎn)臨界點(diǎn)就在 sqrt(n)。
換句話說舱殿，如果在 [2,sqrt(n)] 這個(gè)區(qū)間之內(nèi)沒有發(fā)現(xiàn)可整除因子奥裸，就可以直接斷定 n 是素?cái)?shù)了，因?yàn)樵趨^(qū)間 [sqrt(n),n] 也一定不會(huì)發(fā)現(xiàn)可整除因子沪袭。
現(xiàn)在湾宙，isPrime 函數(shù)的時(shí)間復(fù)雜度降為 O(sqrt(N))，但是我們實(shí)現(xiàn) countPrimes 函數(shù)其實(shí)并不需要這個(gè)函數(shù)冈绊，以上只是希望讀者明白 sqrt(n) 的含義侠鳄，因?yàn)榈葧?huì)還會(huì)用到。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)死宣，手把手刷 200 道力扣題目伟恶，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新毅该。建議收藏知押，按照我的文章順序刷題叹螟，掌握各種算法套路后投再入題海就如魚得水了。
高效實(shí)現(xiàn) countPrimes
高效解決這個(gè)問題的核心思路是和上面的常規(guī)思路反著來：
首先從 2 開始台盯，我們知道 2 是一個(gè)素?cái)?shù)罢绽，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8... 都不可能是素?cái)?shù)了。
然后我們發(fā)現(xiàn) 3 也是素?cái)?shù)静盅，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12... 也都不可能是素?cái)?shù)了良价。
看到這里，你是否有點(diǎn)明白這個(gè)排除法的邏輯了呢蒿叠？先看我們的第一版代碼：
int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
// 將數(shù)組都初始化為 true
Arrays.fill(isPrim, true);
for (int i = 2; i < n; i++)
if (isPrim[i])
// i 的倍數(shù)不可能是素?cái)?shù)了
for (int j = 2 * i; j < n; j += i)
isPrim[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim[i]) count++;
return count;
}
如果上面這段代碼你能夠理解明垢，那么你已經(jīng)掌握了整體思路，但是還有兩個(gè)細(xì)微的地方可以優(yōu)化市咽。
首先痊银，回想剛才判斷一個(gè)數(shù)是否是素?cái)?shù)的 isPrime 函數(shù)，由于因子的對稱性施绎，其中的 for 循環(huán)只需要遍歷 [2,sqrt(n)] 就夠了溯革。這里也是類似的，我們外層的 for 循環(huán)也只需要遍歷到 sqrt(n)：
for (int i = 2; i * i < n; i++)
if (isPrim[i])
...
除此之外谷醉，很難注意到內(nèi)層的 for 循環(huán)也可以優(yōu)化致稀。我們之前的做法是：
for (int j = 2 * i; j < n; j += i)
isPrim[j] = false;
這樣可以把 i 的整數(shù)倍都標(biāo)記為 false，但是仍然存在計(jì)算冗余俱尼。
比如 n = 25抖单，i = 4 時(shí)算法會(huì)標(biāo)記 4 × 2 = 8，4 × 3 = 12 等等數(shù)字遇八，但是這兩個(gè)數(shù)字已經(jīng)被 i = 2 和 i = 3 的 2 × 4 和 3 × 4 標(biāo)記了矛绘。
我們可以稍微優(yōu)化一下，讓 j 從 i 的平方開始遍歷刃永，而不是從 2 * i 開始：
for (int j = i * i; j < n; j += i)
isPrim[j] = false;
PS：我認(rèn)真寫了 100 多篇原創(chuàng)蔑歌，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄揽碘，持續(xù)更新次屠。建議收藏，按照我的文章順序刷題雳刺，掌握各種算法套路后投再入題海就如魚得水了劫灶。
這樣，素?cái)?shù)計(jì)數(shù)的算法就高效實(shí)現(xiàn)了掖桦，其實(shí)這個(gè)算法有一個(gè)名字本昏，叫做 Sieve of Eratosthenes∏雇簦看下完整的最終代碼：
int countPrimes(int n) {
boolean[] isPrim = new boolean[n];
Arrays.fill(isPrim, true);
for (int i = 2; i * i < n; i++)
if (isPrim[i])
for (int j = i * i; j < n; j += i)
isPrim[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrim[i]) count++;
return count;
}
該算法的時(shí)間復(fù)雜度比較難算涌穆，顯然時(shí)間跟這兩個(gè)嵌套的 for 循環(huán)有關(guān)怔昨，其操作數(shù)應(yīng)該是：
n/2 + n/3 + n/5 + n/7 + ...
= n × (1/2 + 1/3 + 1/5 + 1/7...)
括號中是素?cái)?shù)的倒數(shù)。其最終結(jié)果是 O(N * loglogN)宿稀，有興趣的讀者可以查一下該算法的時(shí)間復(fù)雜度證明趁舀。
以上就是素?cái)?shù)算法相關(guān)的全部內(nèi)容。怎么樣祝沸，是不是看似簡單的問題卻有不少細(xì)節(jié)可以打磨呀矮烹？
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目罩锐，建議收藏奉狈！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星涩惑！
