1. 问题背景与理解第一次看到非素数个数这个题目时我正坐在厦门大学计算机实验室里准备机试练习。作为一道经典的算法题它看似简单却暗藏玄机。题目要求我们统计给定区间内非素数的数量这比直接判断素数要绕一个弯子。素数质数是指大于1的自然数中除了1和它本身外没有其他因数的数。而非素数就是除了素数以外的所有自然数包括1和合数即可以分解为多个素数乘积的数。这道题的关键在于如何高效地判断一个数是否为素数然后取反统计。2. 素数判断的常见方法2.1 暴力枚举法最直观的方法是暴力枚举对于一个数n检查2到n-1之间是否有能整除n的数。如果有则n不是素数。def is_prime(n): if n 1: return False for i in range(2, n): if n % i 0: return False return True这种方法的时间复杂度是O(n)对于大数来说效率极低。在机试环境下当n很大时比如10^6这种算法会严重超时。2.2 优化到平方根一个重要的数学观察是如果n不是素数那么它至少有一个因数小于等于√n。因此我们只需要检查到√n即可import math def is_prime(n): if n 1: return False for i in range(2, int(math.sqrt(n)) 1): if n % i 0: return False return True这样时间复杂度降到了O(√n)效率提升显著。这也是面试中最常被问到的素数判断方法。3. 埃拉托斯特尼筛法筛法3.1 筛法原理当需要统计一个区间内非素数的数量时逐个判断每个数是否为素数仍然不够高效。埃拉托斯特尼筛法Sieve of Eratosthenes是更优的选择。筛法的核心思想是从2开始将每个素数的倍数都标记为非素数。这样当我们处理完所有小于等于√n的数后剩下的未被标记的数就是素数。3.2 筛法实现def count_non_primes(n): if n 2: return n is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(math.sqrt(n)) 1): if is_prime[i]: for j in range(i*i, n1, i): is_prime[j] False return n 1 - sum(is_prime)这个算法的时间复杂度是O(n log log n)空间复杂度是O(n)。对于n10^6的情况筛法比逐个判断快约100倍。4. 区间非素数统计4.1 问题变种原题可能要求统计[a, b]区间内的非素数数量而不仅仅是[1, n]。这时我们可以使用筛法生成1到b的所有素数标记统计a到b区间内的非素数数量def count_non_primes_in_range(a, b): if b 2: return b - a 1 is_prime [True] * (b 1) is_prime[0] is_prime[1] False for i in range(2, int(math.sqrt(b)) 1): if is_prime[i]: for j in range(i*i, b1, i): is_prime[j] False return sum(1 for x in range(a, b1) if not is_prime[x])4.2 边界情况处理在实际编程中需要特别注意边界情况a 2时的处理a b时的处理大数情况下的内存优化5. 性能优化技巧5.1 分段筛法当区间很大时比如a1, b10^9传统的筛法会消耗过多内存。这时可以使用分段筛法先用筛法生成小素数如≤√b然后将大区间分成若干段用这些小素数筛选每段5.2 位压缩存储为了节省空间可以用位运算来存储素数标记数组。Python中可以使用bytearrayis_prime bytearray([1]) * (n 1) is_prime[0] is_prime[1] 0这样可以将内存使用减少到原来的1/8。6. 实际测试与验证为了验证我们的算法正确性可以编写测试用例test_cases [ (1, 10, 6), # 非素数1,4,6,8,9,10 (10, 20, 9), # 非素数10,12,14,15,16,18,20 (100, 200, 78), (1000000, 1001000, 920) ] for a, b, expected in test_cases: assert count_non_primes_in_range(a, b) expected7. 常见错误与调试在实现过程中我遇到过几个典型错误边界条件错误忘记处理n0或1的情况循环范围错误筛法内层循环应该从ii开始而不是i2数据类型溢出在C等语言中i*i可能导致整数溢出性能陷阱在Python中sum(is_prime)比循环计数快很多调试时可以打印中间结果比如小范围内的素数标记数组验证筛选是否正确。8. 算法选择建议根据不同的输入规模建议采用不同的策略小范围查询n≤10^6直接使用筛法预处理大范围单次查询使用优化的试除法如Miller-Rabin素性测试超大范围区间查询分段筛法在编程竞赛中通常n≤10^7因此标准筛法是最实用的选择。9. 扩展思考这个问题可以延伸出许多有趣的变种统计半素数两个素数乘积的数量找出最长的连续合数区间计算素数的密度函数研究素数分布的规律理解素数判断和筛法不仅是解决这道题的关键也是许多数论问题的基础。我在准备ACM竞赛时这类题目帮助我深入理解了算法优化的思维方式。