1. 项目概述为什么我们需要素数筛法在编程和算法竞赛中判断一个数是否为素数或者找出一定范围内的所有素数是一个经典且高频的需求。最直观的想法是对于每个待判断的数n用从2到sqrt(n)的所有整数去试除。这种方法被称为“试除法”。对于单个数字试除法效率尚可但一旦问题规模变大比如要求找出1到10^7之间的所有素数试除法的时间复杂度就完全无法接受了。这时素数筛法就成为了我们必须掌握的利器。素数筛法的核心思想是“标记”而非“计算”。它通过某种高效的规则提前将合数非素数标记出来剩下的自然就是素数。这就像在一张名单上划掉所有不符合条件的人而不是一个个去面试每个人。今天要深入探讨的就是两种最经典、应用最广泛的筛法埃拉托斯特尼筛法简称埃氏筛和欧拉筛也称线性筛。它们不仅是解决素数相关问题的“标准答案”其背后蕴含的“空间换时间”和“线性复杂度”思想对于理解更复杂的算法也大有裨益。2. 埃拉托斯特尼筛法直观高效的入门之选埃氏筛以其发明者古希腊数学家埃拉托斯特尼命名其原理非常直观易于理解和实现是学习筛法的绝佳起点。2.1 核心原理与算法步骤算法的核心在于一个素数的所有倍数大于该素数本身必然是合数。我们以一个具体的例子来说明假设我们要找出1到30之间的所有素数。初始化创建一个布尔数组is_prime[0..n]初始时假设所有数都是素数设为True。我们知道0和1不是素数所以先将is_prime[0]和is_prime[1]设为False。开始筛选从第一个素数2开始。将2的所有倍数4, 6, 8, ..., 30标记为合数is_prime[i] False。寻找下一个素数在数组中找到下一个未被标记为合数即is_prime[i]仍为True的数。这个数就是下一个素数这里是3。将3的所有倍数6, 9, 12, ..., 30标记为合数。重复步骤3找到下一个未被标记的数5标记其所有倍数10, 15, 20, 25, 30。何时停止我们不需要一直筛选到n。对于当前素数p如果p * p n那么所有小于等于n的合数都已经被p或更小的素数标记过了。因为任何小于等于n的合数m必然有一个质因子q sqrt(m) sqrt(n)。在上例中5 * 5 25 30我们继续下一个素数是77 * 7 49 30此时即可停止筛选。收集结果遍历is_prime数组所有值为True的索引i就是素数。这个过程就像用筛子一遍遍过滤合数被筛掉素数留在筛子上故名“筛法”。2.2 代码实现与复杂度分析以下是埃氏筛的 Python 实现def eratosthenes_sieve(n): 埃拉托斯特尼筛法返回小于等于 n 的所有素数列表。 is_prime [True] * (n 1) is_prime[0] is_prime[1] False # 0和1不是素数 # 只需遍历到 sqrt(n) for i in range(2, int(n ** 0.5) 1): if is_prime[i]: # 从 i*i 开始标记因为 i*(i-1), i*(i-2)... 已经被更小的素数标记过了 for j in range(i * i, n 1, i): is_prime[j] False # 收集素数 primes [i for i in range(2, n 1) if is_prime[i]] return primes # 示例找出100以内的素数 primes eratosthenes_sieve(100) print(primes[:20]) # 打印前20个素数时间复杂度分析 埃氏筛的时间复杂度是O(n log log n)。这个复杂度已经非常接近线性对于绝大多数应用场景如n 10^7效率极高。推导过程涉及调和级数和对数积分这里我们只需记住结论它的效率远高于对每个数单独试除的O(n sqrt(n))。空间复杂度 需要O(n)的布尔数组来存储标记信息。2.3 埃氏筛的优化与局限性常见优化从i*i开始标记如代码所示对于素数i2*i, 3*i, ..., (i-1)*i这些倍数其质因子包含比i更小的素数因此它们一定在之前轮次的筛选中被标记过了。从i*i开始能减少重复操作。只筛奇数除了2以外所有偶数都是合数。我们可以先单独处理2然后只对奇数进行筛选这样数组大小和遍历次数都能减半。局限性核心缺陷 埃氏筛最大的问题是重复标记。一个合数可能被多个质因子标记多次。例如合数30 2*15 3*10 5*6它会被素数2、3、5各标记一次。当n非常大例如10^8以上时这些重复操作会带来可观的开销。这就引出了我们需要更高效筛法的原因。实操心得在算法竞赛或日常开发中如果问题规模n在10^7量级埃氏筛通常是首选因为它代码简单不易出错且O(n log log n)的复杂度完全够用。记住优化点“从i*i开始”和“只筛奇数”能带来小幅但稳定的性能提升。3. 欧拉筛追求极致的线性算法为了克服埃氏筛的重复标记问题欧拉筛线性筛应运而生。它的核心目标是确保每个合数只被其最小的质因子标记一次从而将时间复杂度严格降到O(n)。3.1 算法原理深度解析欧拉筛的精妙之处在于它维护了一个当前已发现的素数列表并用一种独特的方式来生成合数。算法流程同样初始化一个布尔数组is_prime[0..n]和一个空列表primes用于存放找到的素数。从2开始遍历到n的每一个整数i。如果is_prime[i]为True说明i是素数将其加入primes列表。无论i是否为素数都遍历当前的primes列表即已发现的素数令当前素数为p。计算合数c i * p。标记is_prime[c] False。关键步骤如果i能被p整除即i % p 0则跳出对primes的遍历。为什么这是线性的为什么每个合数只被标记一次关键在于i % p 0这个中断条件。我们通过一个例子来理解。假设i 4primes [2, 3]。取p 2标记4 * 2 8。然后检查4 % 2 0成立跳出循环。不会用p 3去标记4 * 3 12。为什么不让i4去标记12呢因为12的最小质因子是2。我们希望12在i 6时由p 2来标记6 * 2 12。这样就能保证每个合数都由其最小质因子 * 最大因子的组合来唯一生成。更形式化地理解设合数N的最小质因子为p_min令N p_min * k。在欧拉筛的运行过程中N一定会在外层循环i k时在内层循环用p p_min标记。并且由于k % p_min 0在标记完N后循环会立即中断防止后续用更大的质因子去重复标记N。3.2 代码实现与逐行解读def euler_sieve(n): 欧拉筛线性筛返回小于等于 n 的所有素数列表。 is_prime [True] * (n 1) primes [] # 用于存储素数 for i in range(2, n 1): if is_prime[i]: primes.append(i) # i是素数加入列表 # 遍历当前已找到的素数 for p in primes: c i * p if c n: # 生成的合数超过范围中断 break is_prime[c] False # 标记合数 if i % p 0: # 核心保证每个合数只被最小质因子标记一次 break return primes # 示例 primes_linear euler_sieve(100) print(primes_linear[:20])逐行分析for i in range(2, n1): 外层循环遍历每个数。if is_prime[i]: primes.append(i): 如果i未被标记为合数它就是素数。for p in primes:: 内层循环遍历所有已发现的素数。c i * p; if c n: break: 生成合数如果超出范围就停止。is_prime[c] False: 标记这个合数。if i % p 0: break:灵魂所在。一旦发现p能整除i就停止用当前i继续生成合数。这保证了c是被其最小质因子p标记的。3.3 欧拉筛的优势、代价与应用场景优势严格线性时间复杂度 O(n)每个合数只被访问和标记一次。在处理超大范围如n 10^7时性能优势相比埃氏筛会越来越明显。可同步获取素数表算法运行结束后primes列表自然就是有序的素数表无需再遍历收集。代价代码逻辑稍复杂理解其正确性需要一点思考实现时i % p 0这个条件必须正确放置。常数时间可能略大虽然复杂度是线性的但由于内层循环和取模运算在处理中小规模数据如n 10^6时其实际运行时间可能和优化后的埃氏筛相差无几甚至因为常数大而稍慢。应用场景需要极大范围的素数表例如n在10^8量级欧拉筛是唯一选择。需要基于素数筛进行扩展许多数论问题需要在筛法的过程中同步计算一些信息例如每个数的最小质因子、欧拉函数值等。欧拉筛的框架非常适合进行这种“一边筛素数一边打表”的操作因为每个数只被其最小质因子访问一次。注意事项实现欧拉筛时最常见的错误是把if i % p 0: break放在标记合数is_prime[c] False之前。这会导致某些合数特别是质数的平方如4,9,25没有被标记。务必先标记再判断是否跳出。4. 两种筛法的性能对比与实测数据理论分析需要实践验证。我们通过一个简单的测试来感受两者的差异。import time def test_performance(n): print(f测试范围 n {n}) start time.time() primes_e eratosthenes_sieve(n) time_e time.time() - start print(f埃氏筛 耗时: {time_e:.4f} 秒找到素数 {len(primes_e)} 个) start time.time() primes_l euler_sieve(n) time_l time.time() - start print(f欧拉筛 耗时: {time_l:.4f} 秒找到素数 {len(primes_l)} 个) print(- * 40) # 测试不同规模 test_performance(10**6) # 一百万 test_performance(5*10**6) # 五百万 test_performance(10**7) # 一千万可能的输出结果分析具体时间因机器而异测试范围 n 1000000 埃氏筛 耗时: 0.050 秒找到素数 78498 个 欧拉筛 耗时: 0.080 秒找到素数 78498 个 ---------------------------------------- 测试范围 n 5000000 埃氏筛 耗时: 0.350 秒找到素数 348513 个 欧拉筛 耗时: 0.450 秒找到素数 348513 个 ---------------------------------------- 测试范围 n 10000000 埃氏筛 耗时: 0.800 秒找到素数 664579 个 欧拉筛 耗时: 0.950 秒找到素数 664579 个从测试中我们可以观察到结果一致两种算法得到的素数个数完全相同验证了正确性。性能曲线在n达到一千万时欧拉筛的理论线性优势尚未完全压倒埃氏筛的常数优势。这是因为O(n log log n)中的log log n增长极其缓慢log log 10^7 ≈ 3。在n为千万级时两者可视为同一数量级。转折点通常当n超过10^8欧拉筛的线性优势才会变得非常明显。埃氏筛的重复标记操作总量约为n * (1/2 1/3 1/5 ...) ≈ n log log n而欧拉筛严格是n次操作。选择建议n 10^7优先使用埃氏筛。代码简单不易出错性能足够且经过“只筛奇数”等优化后实际速度可能更快。n 10^7或需要同步计算其他函数必须使用欧拉筛。其线性复杂度在面对上亿数据量时是唯一可行的选择并且其框架易于扩展。5. 筛法的经典应用场景与扩展掌握筛法本身不是终点更重要的是运用它来解决实际问题。5.1 素数判定与区间素数查询问题如何快速回答“数字x是否是素数”或“区间[a, b]内有多少素数”。方案预处理筛出足够大范围如sqrt(最大值)或整个区间的素数表之后的所有查询都是O(1)的数组访问。这是典型的“空间换时间”和“预处理”思想。5.2 计算每个数的最小质因子欧拉筛是完成此任务的绝佳工具。我们只需稍作修改def get_min_prime_factors(n): 返回一个数组 min_prime其中 min_prime[i] 表示 i 的最小质因子。 对于素数 imin_prime[i] i。 min_prime [0] * (n 1) primes [] for i in range(2, n 1): if min_prime[i] 0: # i是素数 min_prime[i] i primes.append(i) for p in primes: c i * p if c n: break min_prime[c] p # 记录合数c的最小质因子p if i % p 0: break return min_prime这个min_prime数组非常有用可以用于质因数分解分解N时不断除以min_prime[N]速度极快。计算欧拉函数、约数个数等数论函数。5.3 基于筛法的欧拉函数计算欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的个数。利用欧拉筛我们可以在O(n)时间内计算出1到n所有数的欧拉函数值。def euler_phi_sieve(n): 使用欧拉筛计算1到n的欧拉函数值。 phi [0] * (n 1) is_prime [True] * (n 1) primes [] phi[1] 1 for i in range(2, n 1): if is_prime[i]: primes.append(i) phi[i] i - 1 # 素数i的欧拉函数值为i-1 for p in primes: c i * p if c n: break is_prime[c] False if i % p 0: # 情况1: p是i的质因子则 φ(i*p) φ(i) * p phi[c] phi[i] * p break else: # 情况2: p与i互质则 φ(i*p) φ(i) * φ(p) φ(i) * (p-1) phi[c] phi[i] * (p - 1) return phi5.4 筛法在算法竞赛中的实战技巧内存优化对于极大的n如10^8布尔数组is_prime可能占用数百MB内存。可以使用bitarray或bytearray来压缩内存甚至使用分段筛法Segmented Sieve来突破内存限制在有限内存下筛出超大范围的素数。预处理与缓存在有多组测试用例的题目中如果所有用例的最大n相同那么只需在程序开始时全局执行一次筛法将结果素数表或is_prime数组缓存起来所有查询共享避免重复计算。结合其他算法筛法常作为预处理步骤为更复杂的数论算法如莫比乌斯反演、原根判定提供支持。6. 常见问题与排查技巧实录在实际编码和应用中你可能会遇到以下问题问题1筛法结果错误漏掉了一些素数或包含了合数。排查点1埃氏筛检查外层循环的终止条件是否为i sqrt(n)。写成i n会导致大量无意义的重复标记和逻辑错误。排查点2埃氏筛检查内层标记循环的起始点是否为j i*i。从i*2开始会导致重复标记影响效率但通常不影响正确性但如果同时优化了“只筛奇数”起始点计算错误就会导致漏标。排查点3欧拉筛这是最高频的错误点。确认if i % p 0: break这行代码的位置。它必须放在is_prime[c] False之后。如果放在前面像4, 9, 25这样的平方素数将不会被标记为合数。排查点4通用数组是否初始化正确is_prime[0]和is_prime[1]是否设为False数组大小是否为n1问题2程序在较大输入如n10^7时运行非常慢或内存溢出。性能慢首先确认你使用的是优化后的埃氏筛或欧拉筛。使用试除法嵌套循环肯定会超时。对于Python可以尝试使用bytearray代替list of bool并使用局部变量减少属性查找能提升一定速度。内存溢出计算10^7的布尔列表在Python中大约占用10^7 bytes ≈ 10 MB通常可以接受。如果n更大考虑使用array(B)或bitarray。如果问题要求n极大如10^9但区间长度有限则应使用分段筛法。问题3如何验证筛法结果的正确性小范围交叉验证用最朴素的试除法写一个函数对小范围如n 10000的数据进行验证对比两种方法的结果是否一致。利用已知结论素数定理给出小于n的素数个数近似为n / ln(n)。你可以检查你求得的素数个数是否在这个近似值附近。例如n10^6时素数个数约为78498n10^7时约为664579。检查边界手动验证几个边界素数比如2最小的素数以及你筛选范围内最大的那个素数。问题4欧拉筛中内层循环的条件if c n: break可以优化吗可以。因为c i * p且p 2所以当i n // 2时i * 2 n内层循环一次都不会执行。我们可以在外层循环中增加一个判断if i * primes[0] n: break。但通常这个优化带来的收益很小为了代码清晰可以不做。踩坑记录我曾经在实现欧拉筛时为了“优化”将内层循环写成了for p in primes if i * p n:然后在循环内标记。这看起来简洁但破坏了“遇到i % p 0就跳出”的逻辑顺序因为if条件判断在循环体执行之前。这个错误导致程序在某些输入下结果错误调试了很久。教训是在修改核心算法逻辑时尤其是涉及循环和条件中断时一定要谨慎最好先用小数据暴力对比验证。