问题

给定一个正整数 $n$ ，现在要求出 $1～n$ 的所有质数。

我们之前学过， 质数的定义 ：如果一个数只能被 $1$ 或 它本身 整除，那么它就是 质数 。

判断一个数是否是质数，我们一般的做法：

bool is_prime(int x) {
	if (x < 2) {
		return 0;
	}
	bool res = 1;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			res = 0;
			break;
		}
	}
	return res;
}

之前所学

但是！！！， 如果我们每个数都要这么去判断，那么在 $n$ 非常大的时候每个数都这样去判断，时间复杂度就是O(n $\sqrt{n}$ )必然 超时！！！

欧拉筛法

筛法：筛法 - OI Wiki

其实有一种方法——埃氏筛法，但是同一个质数会被筛多次，这样的做法不够优化。
在传统的埃氏筛中，比如数字 12 ，它会被质数 2 筛除一次（2×6=12 ），又会被质数 3 筛除一次（3×4=12 ），造成了重复计算。而欧拉筛通过一个巧妙的限制条件，确保 12 只被 2 筛除，当遍历到质数 3 时，直接跳过对 12 的操作。

有一种线性筛质数的方法——欧拉筛法
算术基本定理 ： 任何一个大于 1 的合数，都有且仅有一个最小质因子。
核心思想 ：每个数只能被它的 最小质因数 筛去

算法执行逻辑

首先我们要维护一个质数表—— primes ，另外还有一个布尔类型的表用来标记这个数是否是合数—— not_prime ，然后我们遍历 $i$ 从 $2$ 到 $n$ ：

1. 如果 $i$ 是质数，我们直接加入 primes 中；
2. 遍历当前 primes 中的每一个质数 $p$ ，标记 $i\times p$ 为合数；
3. 关键剪枝 ：遍历当前 primes 中的 $p$ 时，如果发现 $p$ 是 $i$ 的因子（即 $i\mathrm{mod}p==0$ ），那么立即停止对 primes 的遍历，不再往后去标记合数。

为什么这个关键的剪枝条件能够保证“每个合数只被最小质因子筛除”？

这是a欧拉筛法i最精髓的部分。 假设 我们当前外层循环到了 $i$ ，内层循环到了 $p$ ，并满足 $i\mathrm{mod}p==0$ 。

• 此时， $p$ 必然是 $i$ 的最小质因子（因为我们的 primes 是从小到大遍历的）
• 令 $i=p\times k$ ，那么当前标记的合数就是 $i\times p=p^2\times k$ 。
• 如果我们此时不停止对合数的标记操作，继续用下一个更大的质数 $p^{\prime }(p^{\prime }>p)$ 去乘 $i$ ，去标记合数 $i\times p^{\prime }=p\times k\times p^{\prime }$ 。
• 注意看这个 新筛除的合数 $p\times k\times p^{\prime }$ ，它的 最小质因子 显然是 $p$ （即 我们是用更大的质数 $p^{\prime }$ 把 $p\times k\times p^{\prime }$ 筛除的，而不是用的它的最小质因子 $p$ ），而不是 $p^{\prime }$ ，因为 $p^{\prime }>p$ 。于是，这个合数就不是被所谓的它的 最小质因子 筛除了， 违背 了我们的 核心思想 ，我们就应该在刚才 $i\mathrm{mod}p==0$ 的时候停止这个标记合数的操作。

完整代码实现

#include <bits/stdc++.h>
#define endl '\n'
#define N 1010
// 假设n最大是1010
using namespace std;

// 目标：求出1~n所有的质数
int n;
// 标记合数的数组
bool not_prime[N];
// 质数数组
vector<int> primes;
int main() {
    cin >> n;
    // 外层循环
    for (int i = 2; i <= n; i++) {
        // 1.如果当前的数字i是质数（即没有被not_prime数组标记），那么n我们就把它放到primes（质数数组）中
        if (!not_prime[i]) {
            primes.push_back(i);
        }
        // 2.遍历primes数组中的质数，进行标记合数的操作
        for (auto p : primes) {
            // 防止筛除质数的时候越界，确保我们只在1到n的范围内筛除
            if (p * i > n) {
                break;
            }
            // 标记p * i为合数
            not_prime[p * i] = 1;
            // 关键剪枝
            if (i % p == 0) {
                break;
            }
        }
    }
    // 输出结果
    for (auto p : primes) {
        cout << p << ' ';
    }
    cout << endl;
    return 0;
}