26.计算素数（较差算法）

一. 问题

编写程序，找出1到100之间的所有素数。

二. 思路

1. 用一个 vector 保存当前找到的素数，这个 vector 称为素数表。

2. 对 1 到 100 之间的每一个数，都用这个vector中的素数去除，如果发现能整除，那么说明当前这个数是合数；如果不能整除，那么就说明当前这个数是素数，并把它加入到这个素数表中。

3. 实际上，我们知道 1 不算质数，而 2 是质数，所以我们从 3 开始计算。（即一开始素数表中只有 2 ，后面逐渐往里添加元素）。

三. 代码实现

void find_prime(vector<int> &primes, int n) {
    for (int i = 3; i <= n; i += 2) {
        bool is_prime = true;
        for (auto &x : primes) {
            if (i % x == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            primes.push_back(i);
        }
    }
}

主函数测试：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> primes { 2 };
    find_prime(primes, 100);

    for (auto &x : primes) {
        cout << x << " " << endl;
    }
    cout << endl;

    return 0;
}

代码中有几处需要说明：

1. 函数中用一个标识变量 is_prime 来判断当前的数是否质数，因为退出循环时，它可能是素数，也可能不是。

2. 从 3 开始，每次向前进 2 步。因为所有的偶数都不是质数，也就没必要每次进一步了。