求n以內(nèi)所有質(zhì)數(shù)的算法及優(yōu)化方法 _所有

文章插圖
問題：輸入一個正整數(shù) N（N > 2），求小于 N 的全部質(zhì)數(shù) 。
【求n以內(nèi)所有質(zhì)數(shù)的算法及優(yōu)化方法】質(zhì)數(shù)，就是除了1和它本身外不存在其他因子的數(shù) 。
1、基本循環(huán)法
循環(huán)法：利用質(zhì)數(shù)的定義，循環(huán)判斷該數(shù)除以比它小的每個自然數(shù)（大于1），如果有能被它整除的，則它就不是質(zhì)數(shù) 。
示例代碼如下：

#include <iostream>using namespace std;int main(){ int N = 50; int sumStep = 0; // 統(tǒng)計迭代次數(shù) cout << 2 << endl; // 2 是質(zhì)數(shù) for (int i = 3; i < N; ++i) { bool flag = true; // 假設(shè)是質(zhì)數(shù) for (int j = 2; j < i; ++j) { sumStep = sumStep + 1; if (!(i % j)) { // 找到能被整除的 flag = false; break; } } if (flag) { cout << i << endl; } } cout << "sumStep: " << sumStep << endl; return 0;}

運(yùn)行結(jié)果如下：

文章插圖
2、算法優(yōu)化
可以看到，當(dāng) N = 50 時，上述算法總共進(jìn)行了349次循環(huán) 。
在上述基本算法的基礎(chǔ)上，可以對循環(huán)進(jìn)行一些優(yōu)化，減少循環(huán)次數(shù)：

對于第一層循環(huán)：除了2之外，偶數(shù)肯定不是質(zhì)數(shù)，因此可以將第一層循環(huán)步數(shù)設(shè)為2；
對于第二層循環(huán)：在第一層循環(huán)的基礎(chǔ)上，因為質(zhì)數(shù)首先肯定是奇數(shù)，所以只需用奇數(shù)整除即可，即第二層循環(huán)步數(shù)也可以設(shè)為2；
對于第二層循環(huán)：判斷一個數(shù) i 是不是質(zhì)數(shù)，只需用 3 到 sqrt(i) 之間的奇數(shù)判斷即可。因為 i 的因數(shù)除了 sqrt(i)，其他都是成對存在的，比如36的因數(shù)（2、3、4、6、9、12、18），36 = 2 * 18；36 = 3 * 12；36 = 4 * 9；36 = 6 * 6；

代碼優(yōu)化如下：

#include <iostream>#include <cmath>using namespace std;int main(){ int N = 50; int sumStep = 0; // 統(tǒng)計迭代次數(shù) cout << 2 << endl; // 2 是質(zhì)數(shù) for (int i = 3; i < N; i += 2) { bool flag = true; // 假設(shè)是質(zhì)數(shù) int jStop = sqrt(i); // 終止條件 for (int j = 3; j <= jStop; j += 2) { sumStep = sumStep + 1; if (!(i % j)) { // 找到能被整除的 flag = false; break; } } if (flag) { cout << i << endl; } } cout << "sumStep: " << sumStep << endl; return 0;}

運(yùn)行結(jié)果如下：