###### tags: `Notes`
# 質數

一個質數(Prime)是一個大於1，
且無法找到除了自己本身和1之外的自然數能整除它的自然數。
舉例來說，2、3、5、7、11、13和17均為質數。

質數是數學上的難題，即便數學已經過幾千年的發展，
卻也還是無法找出一個能完美產生出質數的函數。

## 判斷質數
既然質數無法被除了自己本身和1之外的自然數整除，
只要寫一個迴圈讓 N 除以 從2 到 N-1 的每一個數，
沒有任何一個可以整除的話，就是質數。

function isPrimeNumber(n) {
    if (n > 2) {
        for (let i = 2; i < n; ++i) {
            if (n % i === 0) {
                return false;
            }
        }
        return true;
    } else {
        return n == 2;
    }
}

### 優化 - 排除偶數

- 時間複雜度
(N/2 - 2) + (N/3 - 3) + (N/5 - 5) + ... + (N/sqrtN - sqrtN)
= $\theta(N\log\log N$) 。

function isPrimeNumber(n){
    if(n%2==0){
        n==2;
    }
    else if n > 2 {
    //...
    }
}

### 優化 - [sieve of Eratosthenes](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)
$N$ 若非質數，必有一個小於$\sqrt{N}$ 的因數，所以迴圈跑到 $\sqrt{N} 即可。$

function isPrimeNumber(n) {
    if (n % 2 === 0) {
        return n === 2;
    } else if (n > 2) {
        
        let nSqrt = Math.floor(Math.sqrt(n));  //取根號N
 
        for (let i = 3; i <= nSqrt; i += 2) { //跳過偶數 故 i+=2
            if (n % i === 0) {
                return false;
            }
        }
 
        return true;
    } else {
        return false;
    }
}

### 優化 - 6n $\pm$ 1

- O($n\sqrt{n}$)

這是一個精簡版的篩法，原理是：只拿 2 和 3 這兩個質數先篩過一遍，剩下的數字則用試除法驗證是不是質數。

2 和 3 的最小公倍數是 6 ，我們就把所有數字分為 6n 、 6n+1 、 6n+2 、 6n+2 、 6n+3 、 6n+4 、 6n+5 六種（ n 是倍率）。除以六會餘零的數字為 6n ，除以六會餘一的數字為 6n+1 ，以此類推。

可以看出 6n 、 6n+2 、 6n+3 、 6n+4 會是 2 或 3 的倍數，不屬於質數。因此，只要驗證 6n+1 和 6n+5 是不是質數就可以了。（ 6n+5 也可以寫成 6n-1 ，意義不變。）

6n-1 到 6n+1 ，再到下一個 6n-1 ，再到 6n+1 ，把這些要驗證的數字由小排到大，可以發現之間的差值會是 2 4 2 4 2 4 ... 不斷跳二跳四。實作程式碼時，就可以直接用加法加二加四，而不必用乘法及加減法計算 6n-1 、 6n+1 ，如此一來程式的執行效率會好一點。

驗證的順序是：數字 2 和 3 明顯的是質數，不必驗證；若是從數字 5 開始驗證，那麼下一個要驗證的數字就是 5+2 ，再下一個就是 5+2+4 ，再下一個就是 5+2+4+2 ，如此不斷下去。

function isPrimeNumber(n) {
    if (n === 2 || n === 3) {
        return true;
    } else if (n > 4) {
        let m = n % 6;
 
        if (m !== 1 && m !== 5) {
            return false;
        }
 
        let nSqrt = Math.floor(Math.sqrt(n));
 
        for (let i = 5; i <= nSqrt; i += 6) {
            if (n % i === 0 || n % (i + 2) === 0) { // n % i: 6n + 5 -> 6(n + 1) - 1 -> 6n - 1, n % (i + 2): 6n + 1
                return false;
            }
        }
 
        return true;
    } else {
        return false;
    }
}