1. 素数问题在信息学奥赛中的重要性素数判断与统计一直是信息学奥赛中的经典题型。这类题目看似简单但考察的是选手对算法效率的深刻理解。记得我第一次参加省赛时就遇到了一道需要统计10^6以内素数个数的题目。当时用最朴素的试除法结果程序运行超时惨痛教训让我意识到算法选择的重要性。素数在计算机科学中有着广泛的应用场景。从密码学中的RSA加密算法到哈希表的设计再到分布式系统中的一致性哈希素数的身影无处不在。在竞赛中常见的素数相关题目包括判断单个数是否为素数、统计区间内素数个数、寻找相邻素数对等。其中统计素数个数是最基础的题型也是其他复杂问题的基础。这类题目的难点在于如何在时间限制内完成大规模数据的处理。比如给定n10^6需要统计从2到n之间有多少个素数。直接使用试除法的话时间复杂度是O(n√n)在n较大时必然超时。这时候就需要更高效的筛法来解决。2. 试除法最直观的素数判断方法2.1 算法原理与实现试除法是最容易理解的素数判断算法。它的核心思想是如果一个数n不能被2到√n之间的任何整数整除那么它就是素数。这个结论基于一个简单的数学事实如果n有大于√n的因数那么它必然对应一个小于√n的因数。我们来看一个典型的实现代码bool isPrime(int n) { if(n 2) return false; for(int i 2; i sqrt(n); i) if(n % i 0) return false; return true; }这段代码有几个优化点值得注意只需要检查到√n而不是n-1先处理n2的特殊情况使用sqrt(n)作为循环终止条件而不是i*in这样可避免整数溢出2.2 性能分析与适用场景试除法的时间复杂度是O(√n)每次判断。当需要统计从2到n的所有素数时总时间复杂度为O(n√n)。这在n较小时比如n≤10^4表现尚可但当n增大到10^5甚至10^6时效率就会明显不足。我曾在一次模拟赛中做过测试在n10^5时试除法耗时约0.5秒而n10^6时耗时超过5秒这在竞赛中是无法接受的。因此试除法更适合以下场景只需要判断少量数字是否为素数题目给定的n较小通常n≤10^4作为更复杂算法的组成部分3. 筛法高效统计素数个数的利器3.1 埃拉托斯特尼筛法详解筛法Sieve是更高效的素数统计方法其中最经典的是埃拉托斯特尼筛法。它的基本思路是从2开始将每个素数的倍数都标记为合数这样剩下的就是素数。实现代码如下int countPrimes(int n) { vectorbool isPrime(n1, true); isPrime[0] isPrime[1] false; for(int i 2; i n; i) { if(isPrime[i]) { for(int j i*2; j n; j i) isPrime[j] false; } } int count 0; for(int i 2; i n; i) if(isPrime[i]) count; return count; }这个算法有几个关键优化点外层循环只需要到√n因为更大的数的倍数已经被更小的素数标记过了内层循环可以从ii开始而不是i2因为更小的倍数已经被处理过使用布尔数组而不是整数数组可以节省空间3.2 线性筛法及其优化埃氏筛法的时间复杂度是O(nloglogn)已经比试除法快很多。但还有一种更高效的欧拉筛法线性筛时间复杂度可以达到O(n)。线性筛法的核心思想是确保每个合数只被它的最小质因数筛掉一次。实现代码如下int countPrimes(int n) { vectorint primes; vectorbool isPrime(n1, true); for(int i 2; i n; i) { if(isPrime[i]) primes.push_back(i); for(int j 0; j primes.size() i*primes[j] n; j) { isPrime[i*primes[j]] false; if(i % primes[j] 0) break; } } return primes.size(); }这种算法特别适合需要同时获取素数表和统计素数个数的场景。在我的实际使用中当n10^7时埃氏筛法耗时约0.5秒而线性筛仅需0.2秒左右。4. 算法对比与实战选择4.1 时间复杂度与空间复杂度分析让我们用表格对比三种算法的性能算法时间复杂度空间复杂度适用场景试除法O(n√n)O(1)小规模数据(n≤10^4)埃氏筛O(nloglogn)O(n)中等规模(n≤10^7)线性筛O(n)O(n)大规模数据(n10^7)在实际比赛中还需要考虑代码实现的复杂度和调试难度。埃氏筛虽然理论复杂度不如线性筛但实现简单不易出错在大多数情况下已经足够。4.2 竞赛中的实战建议根据我的参赛经验给出以下建议对于n≤10^4的题目两种方法都可以试除法代码更简单对于10^4n≤10^7的题目优先选择埃氏筛对于n10^7的题目考虑使用线性筛如果题目需要频繁查询素数可以预处理素数表一个常见的优化技巧是预处理素数表。比如在程序开始时先用筛法生成素数表之后的所有查询都可以在O(1)时间内完成。这在需要多次查询的题目中特别有用。另外要注意内存限制。当n非常大时比如10^8布尔数组可能会占用较多内存约100MB。这时候可以考虑使用位运算来压缩存储空间或者分段处理。
