輸出1~n之間的所有質數
寫這篇文章，主要是因為面試的時候碰到該問題，當時沒有反應上來，錯過一個機會，後來思考很久，算是找到一個合理的解決方案，記錄一下。
1. 基本概念
首先，明確一下質數的概念：
質數，又稱素數，指在大於1的自然數中，除了1和它本身以外不再有其他因數。
對應的有一個概念叫合數：
合數，指自然數中除了能被1和本身整除外，還能被其他數（0除外）整除的數。
2. 解題思路
基於這個基本概念，該題目“輸出1~n之前的所有質數”，可以轉化為，迴圈判斷每個數是否為質數。
for (int i = 1; i <= n; i++) {
bool ret = isPrimeNumber(i);
if (ret) {
printf("%d\n", i);
}
}
3. 如何判斷是否為質數
-
a. 最容易實現的方式
判斷是否為質數，主要就是對該數做除法運算，最簡單的想法就是如下所示，n迴圈除以從2到n-1的所有數，如果數可以整除n，則n非質數
bool isPrimeNumber(int n) {
bool ret = true;
for (int i = 2; i < n; i++) {
int remainder = n%i;
if (remainder == 0) {
ret = false;
break;
}
}
return ret;
}
但是該方式有一個主要問題是迴圈太多次，雖然能夠解決問題，但不夠優雅。
-
b. 考慮去除偶數
要對其進行優化，我首先是考慮到除了2以外的偶數肯定是合數，所以判斷質數，首先去掉偶數。判斷是否為偶數有兩種方式：
if (n%2 == 0) return; //根據定義能被2整除即為偶數。
if (n & 0x1 == 0) return; //通過位運算來處理，偶數的最後一位肯定是0x0，和0x1做與運算之後結果為0，從而判斷奇偶性。
一般來說，位運算的效能要優於數學運算，故而可優先考慮第二種方式。
-
c. 考慮縮小除數範圍
首先，上一步排除了被除數中的偶數，故可進一步排除除數中的偶數
for (int i = 3; i < n; ) {
// To do, 判斷是否可整除n
i += 2; //步長為2，即可確保i為奇數。
}
其次，除數不一定要到n-1，其實只需到√n即可，原因如下：
題目資訊：已知n = √n * √n成立，假設n = a * b, a < b，求a的最大值。
推導過程，由題目資訊可得到以下公式：
a * a < a * b = n = a * b < b * b;
=> a < √n < b;
在上述推理中，因為a與b是成對出現的，有一個a存在，必定會有一個b存在，所以找到a就相當於找到b，如果沒有a肯定不存在符合條件的b，故而只判斷n是否被1~√n之前的數整除，即可知道，n是否可被其他數整除。
對於為什麼選擇1-√n，而不是√n-n，原因如下：
題目資訊：已知從1到√n有√n-1-1個數，從√n到n有n-√n-1個數，(比如n=9時，1到√9（即3）中間有3-1-1=1個數2，√9（即3）到9中間有9-3-1=5個數4、5、6、7、8 )，現在需要證明√n-1-1 < n-√n-1。
以下使用逆推法來進行推論，由結論：
√n-1-1 < n-√n-1；
=> √n - 1 < n - √n;
=> 0 < n - 2*√n + 1;
=> 0 < (√n - 1)^2; 小學數學已經學過一個數的平方恆大於等於0，故而該方程式在n>1時恆成立
之前的迴圈可以進一步改進為以下的程式碼：
bool isPrimeNumber(int n) {
bool ret = true;
if (n < 4) return true; //1、2、3肯定為質數
if (n & 0x1 == 0) return false; //排除偶數
int square = (int)sqrt(n);
int i = 3;
while (i <= square) { //除數為從3開始的奇數
int remainder = n%i;
if (remainder == 0) {
ret = false;
break;
}
i += 2;
}
return ret;
}
- d. 其他可以新增的優化
- 需要判斷n是否符合要求，即n>0且為int型，需要考慮n的在編譯時的最大值INT_MAX。
- 如果還想要進一步優化上述程式碼，還想到一個點，因為我們知道除了5之外，其他以5、0結尾的數均可被5整除，0結尾的數已在排除偶數時排除掉了，剩下的就是排除結尾是5的整數，現在想到的方案是將n轉為字串，然後判斷其最後一位（去除'\0'之後）是否為5。不過考慮到能被5整除其實在上述迴圈中也就是多判斷了一次是否可被3整除，並沒有增加很大的工作量，不知道轉為字串後判斷尾數是否能提升效能，在此就不列出實現方案了，如果您感興趣可以自己嘗試對比一下。