PJCHENder 未整理筆記

[演算法] Algorithm: Sieve of Eratosthenes 質數判斷

2017-09-26

[演算法] Algorithm: Sieve of Eratosthenes 質數判斷

@([Udemy] Learning Algorithms in JavaScript from Scratch)[algorithm, javascript]

此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理,但部分程式碼是消化後以自己較易理解的方式重新撰寫,因此和原課程內容有些出入。

問題描述

給予一個數值,把所有小於此數值的質數(Prime)都列出來:

1
2
3
// 以陣列的方式列出小於 number 的所有質數
function sieveOfEratosthenes (number) {...}
sieveOfEratosthenes(20) // [2, 3, 5, 7, 11, 13, 17, 19]

前置知識

質數與合數

數字可以分成質數(Prime)和合數(Composite),而質數的定義是:「一個大於 1 的整數,除了 1 和數本身以外,沒有其他的因數」,質數之外的都屬於合數。

1
2
3
4
5
6
2 = 1 * 2; // 2 是質數
3 = 1 * 2; // 3 是質數
4 = 1 * 4 = 2 * 2; // 4 是合數

5 = 1 * 5; // 5 是質數
6 = 1 * 6 = 2 * 3; // 6 是合數

判斷 N 以內的數是否為質數,只需判斷到 √N 之前有無除了 1 的質因數即可

在判斷一個數字是否為質數前,只需判斷該數目 n 的 1 ~ √n 中有無因數即可,這是什麼意思呢?

假設要判斷 4 以內的所有質數,只需判斷 1 ~ √4 之間有沒有除了 1 的質因數就好。也就是只要判斷 1 ~ 2 有沒有除了 1 是 4 的質因數:

1
4 = 1 * 4 = 2 * 2;

假設要判斷 25 以內的質數,只需要判斷 1 ~ √25 之間有沒有除了 1 的質因數就好。也就是只要判斷 1 ~ 5 有沒有除了 1 是 25 的質因數:

1
25 = 1 * 25 = 5 * 5;

簡單來說:

假如一個數 N 是合數,它有一個因數 a, a × b = N
則 a、b 兩個數中必有一個大於或等於 √N,一個小於或等於 √N。
因此,只要小於或等於 √N 的數中(1 除外)不能整除 N,則 N 一定是質數。
判斷質數合數的「開根號法」的數學原理?怎麼推導的? @ 百度

演算法實做

實做這個演算法的邏輯大致如下,如果我們要取小於 20 以下的質數,那麼我就先建立一個長度為 21 (index 為 0 ~ 20)的陣列,每個元素都代入 true,例如:

1
2
// 若為 `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:

1
2
// 建立一個陣列包含 number + 1 個元素,且元素值均為 true
let isPrimeArr = new Array(n + 1).fill(true);

0 和 1 不是質數

接著,因為我們知道 0 和 1 不是質數,所以:

1
2
3
// 因為我們知道 0 和 1 不是質數
isPrimeArr[0] = false;
isPrimeArr[1] = false;

判斷是否為合數

再來我們要逐字判斷式否為 n 的倍數,是的話表示它是合數:

1
2
3
4
5
6
7
8
9
// 我們只需判斷到 √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 的話,這段迴圈會輸出的結果大概像這樣:

1
2
3
4
5
6
2 的倍數: 4
2 的倍數: 6
2 的倍數: 8
2 的倍數: 10
3 的倍數: 6
3 的倍數: 9

這些倍數都會被標住為 false

把 true 改成 index,把 false 過濾掉

最後可以透過 Array.prototype.map 將 isPrimeArr 中為 true 的內容,代成 index 的值,這時候的陣列會長的像:

1
2
3
4
isPrimeArr = isPrimeArr.map((item, index) => {
return item ? index : false;
});
// [ false, false, 2, 3, false, 5, false, 7, false, false, false ]

接著再透過 Array.prototype.filter 將所有元素為 false 的結果過濾掉

1
2
3
4
// Array.prototype.filter 會把回傳為 true 的陣列元素留下;回傳為 false 的陣列素過濾掉
isPrimeArr = isPrimeArr.filter((item) => item);

// [ 2, 3, 5, 7 ]

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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 ]
*/

資料來源

掃描二維條碼,分享此文章