2017年9月23日 星期六

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

此系列筆記主要依照 [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 一定是質數。
判斷質數合數的「開根號法」的數學原理?怎麼推導的? @ 百度

演算法實做

實做這個演算法的邏輯大致如下,如果我們要取小於 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 意見:

張貼留言