欧拉筛确保每个合数仅被其最小质因子筛一次；通过if(i%primes[j]==0)及时break，避免重复筛，实现线性时间复杂度。
欧拉筛的核心逻辑：每个合数只被最小质因子筛一次
欧拉筛（线性筛）不是靠“标记倍数”来筛，而是用已知质数去生成新合数，并强制要求：只用当前数的最小质因子去筛。关键在于 if (i % primes[j] == 0) 这个判断——一旦成立，立刻 break，防止用更大的质数重复筛同一个合数。
比如筛到 i = 12 时，primes = [2,3,5,...]，先用 2 筛出 12 * 2 = 24；接着用 3，发现 12 % 3 == 0，说明 3 是 12 的最小质因子（因为 12 = 2²×3），再往后用 5 筛 12×5=60 就不对了——60 的最小质因子是 2，它早该在 i=30 时被 2 筛掉。所以必须在此中断。
标准实现模板与关键变量含义
以下是最常用、无冗余的 C++ 实现（std::vector 版本），注意三个核心变量的作用：
std::vector<int> primes;
std::vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) primes.push_back(i);
for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
is_prime[i * primes[j]] = false;
if (i % primes[j] == 0) break;
}
}-
primes：只存质数，顺序即筛出顺序，后续可直接用于质因数分解等 -
is_prime[i]：布尔数组，下标即数字，true表示尚未被筛，最终为质数 i * primes[j] ：防止越界，这是循环终止条件之一，不能省略
常见错误：break 位置错、越界、初始化遗漏
这三个地方写错，筛出来的就不是线性复杂度，甚至结果错误：
立即学习“C++免费学习笔记（深入）”；
- 把
break写在if外面，或漏掉break→ 同一个合数被多次标记，退化成埃氏筛，时间变O(n log log n) -
i * primes[j]没判 n 接近INT_MAX时） - 忘记设
is_prime[0] = is_prime[1] = false→0和1被误认为质数 - 用
int i = 1开始循环 →1 % primes[0]永远不为 0，但1不是质数，且1 * primes[j]会把所有质数本身标为合数
筛完后怎么快速查某个数是不是素数？
筛完后，is_prime[x] 就是 O(1) 查询答案，前提是 x 且已分配足够空间。不要在筛完后再遍历 <code>primes 去二分查找——那是浪费已有的布尔表。
如果只需要质数列表而不需要单点查询，可以省掉 is_prime 数组，只维护 primes，并在内层循环中用 primes[j] 替代 <code>i % primes[j] == 0 的判断逻辑（本质相同，但更难理解）。不过绝大多数场景建议保留 is_prime，清晰且复用性强。
边界值容易被忽略：当 n 时，<code>primes 为空，is_prime 数组长度应为 n+1（哪怕 n=0），否则 is_prime[0] 访问越界。
