此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。
問題描述
給予一個數值，把所有小於此數值的質數（Prime）都列出來：
// 以陣列的方式列出小於 number 的所有質數
function sieveOfEratosthenes (number) {...}
sieveOfEratosthenes(20) // [2, 3, 5, 7, 11, 13, 17, 19]
前置知識
質數與合數
數字可以分成質數（Prime）和合數（Composite），而質數的定義是：「一個大於 1 的整數，除了 1 和數本身以外，沒有其他的因數」，質數之外的都屬於合數。
2 = 1 * 2 // 2 是質數
3 = 1 * 2 // 3 是質數
4 = 1 * 4 // 4 是合數
= 2 * 2
5 = 1 * 5 // 5 是質數
6 = 1 * 6 // 6 是合數
= 2 * 3
判斷 N 以內的數是否為質數，只需判斷到 √N 之前有無除了 1 的質因數即可
在判斷一個數字是否為質數前，只需判斷該數目 n 的 1 ~ √n 中有無因數即可，這是什麼意思呢？
假設要判斷 4 以內的所有質數，只需判斷 1 ~ √4 之間有沒有除了 1 的質因數就好。也就是只要判斷 1 ~ 2 有沒有除了 1 是 4 的質因數：
4 = 1 * 4
= 2 * 2
假設要判斷 25 以內的質數，只需要判斷 1 ~ √25 之間有沒有除了 1 的質因數就好。也就是只要判斷 1 ~ 5 有沒有除了 1 是 25 的質因數：
25 = 1 * 25
= 5 * 5
簡單來說：
假如一個數 N 是合數，它有一個因數 a, a × b = N
則 a、b 兩個數中必有一個大於或等於 √N，一個小於或等於 √N。
因此，只要小於或等於 √N 的數中（1除外）不能整除 N，則 N 一定是質數。
判斷質數合數的「開根號法」的數學原理？怎麼推導的？ @ 百度
則 a、b 兩個數中必有一個大於或等於 √N，一個小於或等於 √N。
因此，只要小於或等於 √N 的數中（1除外）不能整除 N，則 N 一定是質數。
判斷質數合數的「開根號法」的數學原理？怎麼推導的？ @ 百度
演算法實做
實做這個演算法的邏輯大致如下，如果我們要取小於 20 以下的質數，那麼我就先建立一個長度為 21 （index 為 0 ~ 20）的陣列，每個元素都代入 true，例如：
// 若為 `true` 表示它是質數；`false` 則不是質數
let isPrimeArr = [true, true, true, true, true, true, ...]
然後我們由 index 0 開始一個一個判斷，如果它不是質數，則將它改成 false。
- 0, 1 不是質數
- 2 是質數，把所有 2 的倍數都改成 false
- 3 是質數，把所有 3 的倍數都改成 false
- 5 是質數，把所有 5 的倍數都改成 false
- 繼續以此類推
建立一個全都是相同元素的陣列
我們可以用 new Array(length) 來建立一個特定長度的陣列，接著搭配 Array.prototype.fill('<element>') 來把裡面的值都代為 true：
// 建立一個陣列包含 number + 1 個元素，且元素值均為 true
let isPrimeArr = new Array(n + 1).fill(true)
0 和 1 不是質數
接著，因為我們知道 0 和 1 不是質數，所以：
// 因為我們知道 0 和 1 不是質數
isPrimeArr[0] = false
isPrimeArr[1] = false
判斷是否為合數
再來我們要逐字判斷式否為 n 的倍數，是的話表示它是合數：
// 我們只需判斷到 √n 即可
for (var i = 2; i <= Math.sqrt(n); i++) {
// 如果 isPrimeArr[i] 是質數，把所有該倍數都標為非質數
if (isPrimeArr[i] === true) {
for (var j = 2; i * j <= n; j++) {
isPrimeArr[i * j] = false;
}
}
}
假設我們的 n 是 10 的話，這段迴圈會輸出的結果大概像這樣：
2 的倍數: 4
2 的倍數: 6
2 的倍數: 8
2 的倍數: 10
3 的倍數: 6
3 的倍數: 9
這些倍數都會被標住為 false
把 true 改成 index，把 false 過濾掉
最後可以透過 Array.prototype.map 將 isPrimeArr 中為 true 的內容，代成 index 的值，這時候的陣列會長的像：
isPrimeArr = isPrimeArr.map((item, index) => {
return item ? index : false
})
// [ false, false, 2, 3, false, 5, false, 7, false, false, false ]
接著再透過 Array.prototype.filter 將所有元素為 false 的結果過濾掉
// Array.prototype.filter 會把回傳為 true 的陣列元素留下；回傳為 false 的陣列素過濾掉
isPrimeArr = isPrimeArr.filter(item => item)
// [ 2, 3, 5, 7 ]
完整程式碼
function sieveOfEratosthenes (n) {
// 建立一個陣列包含 number + 1 個元素，且元素值均為 true
let isPrimeArr = new Array(n + 1).fill(true)
// 因為我們知道 0 和 1 不是質數
isPrimeArr[0] = false
isPrimeArr[1] = false
// 我們只需判斷到 √n 即可
for (var i = 2; i <= Math.sqrt(n); i++) {
// 如果 isPrimeArr[i] 是質數，把所有該倍數都標為非質數
if (isPrimeArr[i] === true) {
for (var j = 2; i * j <= n; j++) {
console.log(`${i} 的倍數: ${i * j}`)
isPrimeArr[i * j] = false;
}
}
}
/**
* 透過 arr.map 將 isPrimeArr 中為 true 的內容，代成 index 的值
* 透過 arr.filter 將陣列中的 false 都過濾掉
**/
console.log()
return isPrimeArr.map((item, index) => {
return item ? index : false
}).filter(item => item)
}
console.log(sieveOfEratosthenes(100))
/*
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]
*/
0 意見:
張貼留言