问题：输入一个正整数 N（N > 2），求小于 N 的全部质数。

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

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;
}

运行结果如下：

2、算法优化

可以看到，当 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次，大大减少了循环次数，提升了算法效率。