質數判斷

質數：對于所有大于 1 的自然數而言，如果該數除 1 和自身以外沒有其它因數 / 約數，則該數被稱為為質數，質數也叫素數。

如何判定一個數是否為質數呢？

一個簡單的方法是 試除法 ： 對于一個數 n， 可以枚舉 [ 2, n-1 ] 區間內所有數，去嘗試整除 n，如果在區間內存在一個數能將 n 整除，則 n 不是質數。

還要注意一個點 ： 最小的質數是 2，小于 1 的數不是質數。

所以，代碼如下：

bool isPrime(int n){if(n <= 1) return false;for(int i = 2; i < n; i++){if(n % i == 0) return false;}return true;
}

那么上述代碼還能優化嗎？答案是 可以 。

如果按照上面的代碼運行的話，對于一個數，我們將它所有的約數全都枚舉了一遍，到底有沒有必要呢？

下面舉個例子： 例如12，顯然12不是質數， 它的因數有1、2、3、4、6、12，我們可以發現他的因數是成對出現的，(1, 12)、(2, 6)、(3, 4)，那我們能不能只枚舉小的那一個因數呢，這樣就算是一個質數，當我們枚舉一直到 $\sqrt{n}$ ，我們發現沒有符合條件的因子時就不用再向下枚舉了，因為一個合數的因子都是成對出現的。

所以 for 循環中的條件可以寫成這樣 :

i $\le$ $\sqrt{n}$

但是一個數的平方根不一定是一個整數，所以我們還可以這樣寫：

i $?$ i $\le$ n

有的時候，當 n 很大的時候， i$?$i 有可能會超內存，可以改為 :

i $\le$ n / i

當然還有一點很重要，不要忘了 4、9、16、25 等等這種是一個數平方的要特別注意

最終代碼

bool isPrime(int n){if(n <= 1) return false;for(int i = 2; i <= n/i; i++){if(n % i == 0) return false;}return true;
}