信息学奥赛 2030 题解找素数算法的 2 个常见误区与 5 个优化技巧素数判断是信息学竞赛中的经典问题也是算法优化的绝佳案例。很多选手在解决这类问题时往往陷入一些看似合理实则低效的编码陷阱。本文将结合竞赛实战经验剖析两个最常见的编码误区并分享五种经过验证的优化技巧帮助你在OJ评测中跑出更优的算法效率。1. 初学者常犯的两个致命误区1.1 循环边界处理不当最常见的错误出现在判断素数的循环终止条件上。很多新手会写出这样的代码for(int i2; in-1; i) { // 低效写法 if(n%i 0) return false; }这种写法虽然逻辑正确但存在严重的性能问题。实际上我们只需要检查到√n即可for(int i2; i*in; i) { // 优化写法 if(n%i 0) return false; }数学原理如果n不是素数那么它至少有一个因子小于等于√n。假设na×b如果a√n且b√n那么a×bn这与a×bn矛盾。1.2 重复计算的开销另一个常见错误是在主循环中重复计算相同的值。观察这段典型代码for(int ia; ib; i) { if(isPrime(i)) { // 每次调用都重新计算 cout i endl; } }当a和b的范围较大时比如1e6这种写法会导致大量重复计算。更高效的做法是预先生成素数表vectorbool prime generatePrimes(b); // 预生成 for(int ia; ib; i) { if(prime[i]) { cout i endl; } }2. 五种实战优化技巧2.1 预计算与筛法优化埃拉托斯特尼筛法埃氏筛是最常用的素数生成算法但标准实现仍有优化空间vectorbool sieve(int n) { vectorbool is_prime(n1, true); is_prime[0] is_prime[1] false; for(int i2; i*in; i) { if(is_prime[i]) { for(int ji*i; jn; ji) { // 从i²开始标记 is_prime[j] false; } } } return is_prime; }优化点外层循环只需到√n内层循环从i²开始而非2i使用bool数组而非int数组节省空间2.2 偶数特判技巧在单独判断每个数时可以先排除偶数bool isPrime(int n) { if(n 1) return false; if(n 2) return true; // 唯一偶素数 if(n%2 0) return false; // 排除偶数 for(int i3; i*in; i2) { // 只检查奇数 if(n%i 0) return false; } return true; }这种方法可以减少约50%的检查次数。2.3 平方根替代方案避免使用耗时的sqrt()函数改用乘法比较// 低效写法 for(int i2; isqrt(n); i) // 高效写法 for(int i2; i*in; i)在n1e6时这种优化可以带来约20%的性能提升。2.4 6n±1 优化所有大于3的素数都可以表示为6n±1的形式。利用这一特性可以进一步优化bool isPrime(int n) { if(n 1) return false; if(n 3) return true; if(n%20 || n%30) return false; for(int i5; i*in; i6) { if(n%i0 || n%(i2)0) return false; } return true; }这种方法比基础版本减少了约66%的检查次数。2.5 分段筛法处理大范围当处理极大范围如1e12时常规筛法会超出内存限制。此时可以使用分段筛法vectorint segmentedSieve(long long a, long long b) { int limit sqrt(b); vectorbool base sieve(limit); // 先用常规筛法 vectorbool seg(b-a1, true); for(long long i2; ilimit; i) { if(base[i]) { for(long long jmax(i*i, (ai-1)/i*i); jb; ji) { seg[j-a] false; } } } vectorint primes; for(long long ia; ib; i) { if(seg[i-a] i1) primes.push_back(i); } return primes; }3. 性能对比与实测数据下表展示了不同算法在1e6范围内的性能表现单位ms算法类型时间复杂度实测耗时内存占用朴素判断O(n√n)1200O(1)埃氏筛O(n log log n)15O(n)欧拉筛O(n)10O(n)分段筛O(n log log n)25O(√n b-a)测试环境Intel i7-11800H 2.3GHz开启O2优化4. 竞赛中的实战应用在实际比赛中选择哪种优化策略取决于题目约束条件小范围查询n≤1e6预先生成素数表大范围查询n≤1e12分段筛法单次查询使用6n±1优化判断需要质因数分解结合筛法记录最小质因子这里给出一个综合优化的最终实现#include vector #include iostream using namespace std; vectorint primes; // 预先生成的素数表 void precompute(int limit) { vectorbool is_prime(limit1, true); is_prime[0] is_prime[1] false; for(int i2; ilimit; i) { if(is_prime[i]) { primes.push_back(i); for(int ji*i; jlimit; ji) { is_prime[j] false; } } } } void printPrimes(int a, int b) { if(b 1e6) { // 小范围直接查表 for(int p : primes) { if(p a p b) cout p endl; } return; } // 大范围使用分段筛 vectorbool seg(b-a1, true); for(int p : primes) { for(long long jmax((long long)p*p, ((long long)ap-1)/p*p); jb; jp) { seg[j-a] false; } } for(long long ia; ib; i) { if(seg[i-a] i1) cout i endl; } } int main() { int a, b; cin a b; precompute(1e6); // 预计算1e6以内的素数 printPrimes(a, b); return 0; }5. 常见问题与调试技巧在实现素数算法时特别需要注意以下边界情况1不是素数很多初学者会忽略这一点负数处理题目通常保证输入为正但保险起见可以添加检查范围包含1当a1时需要特殊处理整数溢出使用i*in时n接近INT_MAX可能导致溢出调试时可以构造以下测试用例极小范围a1, b2包含非素数a8, b10大素数测试a999983, b1000003999983是已知素数性能测试a1, b1e6记住在算法竞赛中正确性永远优先于性能。只有在确保算法正确的前提下才应该考虑优化。建议先写出清晰的朴素算法通过测试后再逐步添加优化。