埃拉托斯特尼筛法（埃氏筛）

埃拉托斯特尼筛法通过标记非质数的倍数来筛选质数。初始化时假设所有数均为质数，从2开始遍历，若当前数为质数，则标记其所有倍数为非质数。

时间复杂度：

• 朴素实现：$O(n \log \log n)$
• 优化版本（仅遍历到$\sqrt{n}$）：$O(n \log \log n)$

代码实现：

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

题目1：统计区间内的质数数量
问题描述：给定区间$[L, R]$，统计其中质数的数量（$1 \leq L \leq R \leq 10^6$）。
解题思路：预先生成$[1, R]$的质数表，利用前缀和数组快速查询区间和。
代码：

vector<int> preprocess(int max_n) {
    vector<bool> is_prime = sieve(max_n);
    vector<int> prefix(max_n + 1, 0);
    for (int i = 2; i <= max_n; ++i) {
        prefix[i] = prefix[i - 1] + (is_prime[i] ? 1 : 0);
    }
    return prefix;
}

题目2：最小质因数之和
问题描述：给定$n$，求所有数$[2, n]$的最小质因数之和（$n \leq 10^6$）。
解题思路：在埃氏筛过程中记录每个数的最小质因数。
代码：

vector<int> min_prime_factors(int n) {
    vector<int> spf(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        if (spf[i] == 0) {
            spf[i] = i;
            for (int j = i * i; j <= n; j += i) {
                if (spf[j] == 0) spf[j] = i;
            }
        }
    }
    return spf;
}

---

欧拉筛法（线性筛）

欧拉筛法通过保证每个合数仅被其最小质因数标记一次，达到线性时间复杂度。

时间复杂度：$O(n)$

代码实现：

vector<int> euler_sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) break; // 关键：保证只被最小质因数标记
        }
    }
    return primes;
}

题目1：质数间距
问题描述：给定$n$，找到相邻质数差的最大值（$n \leq 10^7$）。
解题思路：生成质数列表后遍历相邻差值。
代码：

int max_gap(int n) {
    vector<int> primes = euler_sieve(n);
    int max_diff = 0;
    for (int i = 1; i < primes.size(); ++i) {
        max_diff = max(max_diff, primes[i] - primes[i - 1]);
    }
    return max_diff;
}

题目2：质数的二进制表示
问题描述：统计$[1, n]$中质数的二进制表示中1的个数也为质数的数量（$n \leq 10^6$）。
解题思路：结合欧拉筛和位运算。
代码：

int count_prime_bits(int n) {
    vector<int> primes = euler_sieve(n);
    int cnt = 0;
    for (int p : primes) {
        int bits = __builtin_popcount(p);
        if (bits >= 2 && is_prime[bits]) cnt++;
    }
    return cnt;
}

---

分段筛法

用于处理大区间质数问题（如$[L, R]$，$R \leq 10^{12}$但$R-L \leq 10^6$）。

步骤：

1. 预生成$\sqrt{R}$内的质数表。
2. 用这些质数标记$[L, R]$内的合数。

代码实现：

vector<bool> segmented_sieve(long long L, long long R) {
    vector<bool> is_prime(R - L + 1, true);
    if (L == 1) is_prime[0] = false;
    for (long long p : euler_sieve(sqrt(R))) {
        for (long long j = max(p * p, (L + p - 1) / p * p); j <= R; j += p) {
            is_prime[j - L] = false;
        }
    }
    return is_prime;
}

题目1：区间质数查询
问题描述：查询$Q$次区间$[L, R]$的质数数量（$Q \leq 1000$，$R \leq 10^{12}$）。
解题思路：对每个查询调用分段筛。
代码：

int query_segmented(int L, int R) {
    vector<bool> seg = segmented_sieve(L, R);
    return count(seg.begin(), seg.end(), true);
}

题目2：相邻质数对
问题描述：在$[L, R]$内统计满足$p$和$p+2$均为质数的对数（$R \leq 10^9$）。
解题思路：分段筛后检查相邻位置。
代码：

int count_twin_primes(long long L, long long R) {
    vector<bool> seg = segmented_sieve(L, R + 2);
    int cnt = 0;
    for (long long i = L; i <= R; ++i) {
        if (seg[i - L] && seg[i + 2 - L]) cnt++;
    }
    return cnt;
}

---

概率性检测（Miller-Rabin）

用于大数质数检测，基于费马小定理和二次探测定理。

时间复杂度：$O(k \log^3 n)$（$k$为测试轮数）

代码实现：

bool miller_rabin(long long n, int k = 5) {
    if (n <= 1) return false;
    for (int p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}) {
        if (n % p == 0) return n == p;
    }
    long long d = n - 1, s = 0;
    while (d % 2 == 0) d /= 2, s++;
    for (int i = 0; i < k; ++i) {
        long long a = rand() % (n - 2) + 2;
        long long x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        for (int j = 0; j < s - 1; ++j) {
            x = mul_mod(x, x, n);
            if (x == n - 1) break;
        }
        if (x != n - 1) return false;
    }
    return true;
}

题目1：大质数验证
问题描述：判断$n$是否为质数（$n \leq 10^{18}$）。
解题思路：直接调用Miller-Rabin。

题目2：安全素数生成
问题描述：生成一个$k$位安全素数（$p=2q+1$且$q$为质数）。
解题思路：随机生成$q$并用Miller-Rabin验证。

---

每种筛法适用于不同场景：埃氏筛适合预处理小范围，欧拉筛适合线性时间需求，分段筛处理大区间，Miller-Rabin用于大数检测。

对比总结

1. 埃拉托斯特尼筛法

   • 实现简单，适合小范围质数生成。
   • 内存占用较高，不适用于极大范围。

2. 欧拉筛法

   • 线性时间复杂度，适合需要高效生成质数的场景。
   • 需额外存储质数列表，但总体空间可控。

3. 分段筛法

   • 适用于极大范围（如 [1e12, 1e12 + 1e6]）。
   • 需预处理小质数基，实现稍复杂。

根据具体需求选择算法：小范围用埃氏筛，线性时间需求用欧拉筛，大范围用分段筛。