埃式筛法模板

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

const int N = 10000010;
bool notPrime[N];
int primes[N], cnt;

void sieve(int n) {
    notPrime[0] = notPrime[1] = true;
    for (int i = 2; i * i <= n; i++) {
        if (!notPrime[i]) {
            for (int j = i * i; j <= n; j += i)
                notPrime[j] = true;
        }
    }
    for (int i = 2; i <= n; i++)
        if (!notPrime[i]) primes[cnt++] = i;
}

int main() {
    int n = 100;
    sieve(n);
    cout << "素数个数: " << cnt << endl;  // 25
    for (int i = 0; i < cnt; i++)
        cout << primes[i] << " ";
    return 0;
}

📖 要点说明

• 从 i*i 开始标记，不是 i*2（后者正确但慢）
• 时间 O(n log log n)，对 n≤10⁷ 足够
• 空间 O(n)

⚠️ 常见错误

• 从 i*2 开始标记效率低但不算错
• 筛的边界 i*i <= n 不是 i <= n
• 忘初始化 notPrime[0] 和 notPrime[1]