埃拉托斯特尼筛法埃氏筛埃拉托斯特尼筛法通过标记非质数的倍数来筛选质数。初始化时假设所有数均为质数从2开始遍历若当前数为质数则标记其所有倍数为非质数。时间复杂度朴素实现$O(n \log \log n)$优化版本仅遍历到$\sqrt{n}$$O(n \log \log n)$代码实现vectorbool sieve(int n) { vectorbool 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]$的质数表利用前缀和数组快速查询区间和。代码vectorint preprocess(int max_n) { vectorbool is_prime sieve(max_n); vectorint 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$。解题思路在埃氏筛过程中记录每个数的最小质因数。代码vectorint min_prime_factors(int n) { vectorint 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)$代码实现vectorint euler_sieve(int n) { vectorbool is_prime(n 1, true); vectorint 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) { vectorint 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) { vectorint 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$。步骤预生成$\sqrt{R}$内的质数表。用这些质数标记$[L, R]$内的合数。代码实现vectorbool segmented_sieve(long long L, long long R) { vectorbool 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) { vectorbool seg segmented_sieve(L, R); return count(seg.begin(), seg.end(), true); }题目2相邻质数对问题描述在$[L, R]$内统计满足$p$和$p2$均为质数的对数$R \leq 10^9$。解题思路分段筛后检查相邻位置。代码int count_twin_primes(long long L, long long R) { vectorbool 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$位安全素数$p2q1$且$q$为质数。解题思路随机生成$q$并用Miller-Rabin验证。每种筛法适用于不同场景埃氏筛适合预处理小范围欧拉筛适合线性时间需求分段筛处理大区间Miller-Rabin用于大数检测。对比总结埃拉托斯特尼筛法实现简单适合小范围质数生成。内存占用较高不适用于极大范围。欧拉筛法线性时间复杂度适合需要高效生成质数的场景。需额外存储质数列表但总体空间可控。分段筛法适用于极大范围如[1e12, 1e12 1e6]。需预处理小质数基实现稍复杂。根据具体需求选择算法小范围用埃氏筛线性时间需求用欧拉筛大范围用分段筛。