問題：輸入一個正整數 N（N > 2），求小于 N 的全部質數。

質數，就是除了1和它本身外不存在其他因子的數。

循環法：利用質數的定義，循環判斷該數除以比它小的每個自然數（大于1），如果有能被它整除的，則它就不是質數。

示例代碼如下：

#include <iostream> using namespace std; int main() { int N = 50; int sumStep = 0; // 統計叠代次數 cout << 2 << endl; // 2 是質數 for (int i = 3; i < N; i) { bool flag = true; // 假設是質數 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; }

運行結果如下：

可以看到，當 N = 50 時，上述算法總共進行了349次循環。

在上述基本算法的基礎上，可以對循環進行一些優化，減少循環次數：

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

代碼優化如下：

#include <iostream> #include <cmath> using namespace std; int main() { int N = 50; int sumStep = 0; // 統計叠代次數 cout << 2 << endl; // 2 是質數 for (int i = 3; i < N; i = 2) { bool flag = true; // 假設是質數 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; }

運行結果如下：

優化後，隻需31次循環，相比原來的349次，大大減少了循環次數，提升了算法效率。

算法分析：時間和空間複雜度

判斷兩正整數是否互質：Matlab求商法

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!