從LeetCode學演算法 - 47 Array (10)

0204. Count Primes (Easy)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

Count the number of prime numbers less than a non-negative number, *n *.

Example:

1
2
3
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

給定一個非負整數n，試求所有小於這個n的質數。

讓我們來複習一下國中(還是國小？)數學：
質數的定義就是除了1和自己 以外，沒有其他數可以整除它的正整數。

透過這個特點我們可以再延伸：
因為合成數必然可以拆成質數相乘 ，
所以我們要判定某個數是否是質數的話，
只要將其他比它小的質數 測試它是否是目標的因數 即可。

另外，由於一個數若能拆成2數相乘，
那麼其中一個因數會小於等於這個數的開根號 ；
另一個因數則是大於等於這個數的開根號 。
如此一來，我們只要檢驗2**~目標數的開根號** 的數是否能整除目標數 即可。

所以老師會教你一個消去法：
首先將2的倍數排除掉，再將3的倍數排除掉，
再將5的倍數排除掉……(2倍以上，不含自己)
一個個操作，走到沒有被排除掉的數即為質數 。

我們可以再進一步處理一點：
假設現在處理到i，
那麼其實我們應該知道i*2, i*3, …, i*(i-1 )的部分，
應該都被前面的操作排除了，
故每次我們只要從i*i開始，排除到n，
也就是i走到最大n的開根號即可。

故整個程式會從2到根號n，每次將對應i的i倍以上的部分設為非質數，
最後計算總質數有多少個。

Java的部分，由於boolean預設為false，
這邊使用nPrime代表not prime，所以nPrime為false代表這個數是質數，
要設定成不是質數時請用nPrime[j] = true。
在處理完後請記得bound後面的質數個數要記得加起來。

Python的部分，sqrt可以直接用n ** 0.5，
並且我們可以用1代表質數，0代表非質數，
讀者可以仔細看一下第8行，其實和Java迴圈的目的是一樣的，
不過這邊直接最後才算prime陣列的總和來取得質數個數。

「時間/空間複雜度？」
(O(n), O(n log log n))
(外層迴圈的boundary上限是sqrt(n)，
內層j的次數上限會從n/2 -> sqrt(n)，具體計算我也不會XD
以Wikipedia提供的時間複雜度為O(n log log n)。
https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)

Special Thanks suggestions/corrections from viewers:
Python Taiwan, 林宣丞：此篩選方式又稱 埃拉托斯特尼篩法(sieve of Eratosthenes)。

(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

1
2
如果你／妳非常喜歡這篇文章，可以按著拍手直到50下。
也請記得「Follow」我，隨時收看最新的文章。