质数与筛法CSP-J

💡 核心思想

质数是大于 1 且只能被 1 和自身整除的整数。筛法用于快速找出 $[1, n]$ 内的所有质数。埃氏筛 $O(n \log \log n)$，欧拉筛（线性筛）$O(n)$。质因数分解也是常见操作。

🎯 直觉理解

筛法就像"排除法"。你要找 1 到 100 里的质数。先把 2 的倍数划掉（4,6,8...），再把 3 的倍数划掉（6,9,12...），以此类推。最后剩下的就是质数。欧拉筛更聪明——它确保每个合数只被划掉一次，不多不少。

📝 算法流程

1. 埃氏筛：标记每个质数的倍数
2. 欧拉筛：每个合数只被最小质因子筛一次
3. 质因数分解：试除法 $O(\sqrt{n})$
4. 判定质数：试除法或 Miller-Rabin

$$\text{埃氏筛复杂度：} O(n \log \log n) \approx O(n)$$

$$\text{欧拉筛复杂度：} O(n)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
const int N = 10000005;
bool notPrime[N]; int primes[N], cnt = 0;
void eulerSieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && (long long)i * primes[j] <= n; j++) {
            notPrime[i * primes[j]] = true;
            if (i % primes[j] == 0) break; // 关键：保证每个合数只被筛一次
        }
    }
}
int main() {
    int n; cin >> n;
    eulerSieve(n);
    cout << cnt << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目