线性筛法模板

#include <bits/stdc++.h>
using namespace std;

const int N = 100000010;
bool vis[N];
int primes[N], cnt;

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && (long long)i * primes[j] <= n; j++) {
            vis[i * primes[j]] = true;
            if (i % primes[j] == 0) break;  // 关键：保证每个合数只筛一次
        }
    }
}

int main() {
    sieve(1000000);
    cout << cnt << endl;  // 78498
    return 0;
}

📖 要点说明

• 严格 O(n)，每个合数只被最小质因子筛一次
• i % primes[j] == 0 时 break 是关键
• 适合 n≤10⁸ 的大规模筛素数

⚠️ 常见错误

• 忘 break 导致重复筛（虽然结果对，但不是线性的）
• i * primes[j] 溢出，需转 long long
• primes 数组大小不够