1. 项目概述从“完数难题”看质数模块的实战价值最近在整理ACM的解题笔记翻到Day7的质数与完数专题发现不少朋友对这两个看似基础的概念在实际编程题中的应用感到头疼。尤其是当题目要求处理大范围数据或者将质数性质与“完数”这类特殊数结合时很多人的第一反应就是暴力循环结果不是超时就是内存溢出。我自己在早期刷题时也踩过不少坑比如试图用最朴素的试除法去筛一千万以内的素数结果程序直接卡死。今天我就结合“完数难题”这个具体的切入点把质数素数模块的核心算法、优化技巧以及它们如何应用于解决复杂问题系统地梳理一遍。无论你是正在备战ACM的新手还是想巩固数论基础的开发者相信这篇从实战出发的总结都能给你带来直接的帮助。所谓“完数”又称完全数是指一个数恰好等于它所有真因子即除了自身以外的正因子之和。比如612328124714。而质数则是只有1和它本身两个正因子的数。这两者看似独立但在算法题中常常被结合起来考察例如判断一个数是否为完数就需要高效找出其所有真因子这其中就涉及到因式分解而质数判断与筛法是高效分解的基础。我们今天的讨论将不止步于概念而是深入到代码实现、性能优化和解题策略中。2. 核心算法原理与选型逻辑在解决涉及质数和完数的ACM题目时算法选型直接决定了程序的生死。下面我们拆解几个核心算法并解释为什么在特定场景下要这么选。2.1 质数判断从试除法到Miller-Rabin最基础的质数判断问题是给定一个整数n判断它是否为质数。1. 朴素试除法这是最直观的想法用2到n-1的每个数去试除n如果都不能整除n就是质数。时间复杂度O(n)。def is_prime_naive(n): if n 2: return False for i in range(2, n): # 从2遍历到n-1 if n % i 0: return False return True注意这种方法仅适用于教学和理解概念对于n稍大比如超过10^5的情况就完全不可用。2. 优化试除法一个关键的数学优化如果n是一个合数那么它必定有一个不大于√n的质因子。因此我们只需要试除到√n即可。时间复杂度降为O(√n)。import math def is_prime_optimized(n): if n 2: return False # 单独处理偶数加速 if n % 2 0: return n 2 # 从3开始步长为2只检查奇数 limit int(math.isqrt(n)) # Python 3.8 使用 isqrt 获取整数平方根 for i in range(3, limit 1, 2): if n % i 0: return False return True为什么有效假设n a * b且a ≤ b。那么a ≤ √n。只要检查完所有≤√n的数就足以判断n是否为合数。单独处理偶数和步长为2的循环是基于“除了2以外所有质数都是奇数”的事实能减少近一半的循环次数。3. Miller-Rabin素性测试当n非常大比如超过10^14时O(√n)的复杂度依然太高。这时需要概率性算法Miller-Rabin是最常用的一种。它是一个多项式时间算法基于费马小定理和二次探测定理。虽然理论上是概率算法但通过选择特定的底数集合对于一定范围内的整数如小于2^64可以做到确定性判断。def miller_rabin(n, k5): # k为测试轮数增加可提高准确性 if n 2: return False for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]: if n % p 0: return n p d n - 1 s 0 while d % 2 0: d // 2 s 1 for _ in range(k): a random.randrange(2, n - 1) x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x (x * x) % n if x n - 1: break else: return False return True选型逻辑n 10^6使用优化试除法代码简单结果绝对正确。10^6 n 10^12可以考虑用预处理的小质数表如前1000个质数先试除再用优化试除法能过滤掉大部分合数。n 10^12或需要极高性能使用Miller-Rabin素性测试。在ACM竞赛中对于64位整数范围内的确定性判断通常使用固定的一组底数如[2, 325, 9375, 28178, 450775, 9780504, 1795265022]即可。2.2 质数筛法埃氏筛与欧拉筛当题目要求找出某一范围内如1到n的所有质数时逐个判断的效率太低需要使用筛法。1. 埃拉托斯特尼筛法埃氏筛核心思想从2开始将每个质数的倍数标记为合数。def sieve_of_eratosthenes(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: # 从i*i开始标记因为i*(i-1)等已被更小的质数标记过 for j in range(i * i, n 1, i): is_prime[j] False primes [i for i in range(2, n1) if is_prime[i]] return primes时间复杂度O(n log log n)。空间复杂度O(n)。为什么从i*i开始对于当前质数i比ii小的合数ikki一定已经被更小的质数比如k的质因子标记过了。这是一个重要的优化点能减少重复标记。2. 欧拉筛线性筛埃氏筛的一个问题是有些合数会被多个质数重复标记如6会被2和3都标记。欧拉筛保证了每个合数只被其最小质因子标记一次从而达到线性时间复杂度O(n)。def euler_sieve(n): is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) for p in primes: if i * p n: break is_prime[i * p] False if i % p 0: # 关键保证每个合数只被最小质因子筛掉 break return primes关键点解析if i % p 0: break这行代码是欧拉筛的灵魂。当p能整除i时说明p是i的最小质因子因为primes是递增的。那么对于后续更大的质数pi * p的最小质因子应该是p而不是p所以应该留到后面当i增长到某个倍数时由p来筛掉现在不能筛否则就重复了。选型逻辑埃氏筛实现简单效率足够应对大部分题目n在10^7以内。在内存允许的情况下是首选。欧拉筛当n非常大接近10^7或更大且需要严格线性时间复杂度或者需要同步获取每个数的最小质因子用于后续快速因式分解时使用。欧拉筛稍复杂但性能更优。2.3 完数判断与因式分解判断一个数n是否为完数需要计算其所有真因子之和。最直接的方法是遍历1到n-1求和复杂度O(n)不可取。高效方法成对枚举因子。 性质如果d是n的因子那么n/d也是n的因子。我们只需要枚举到√n即可。def get_sum_of_proper_divisors(n): if n 1: return 0 total 1 # 1是所有大于1的数的因子 limit int(math.isqrt(n)) for i in range(2, limit 1): if n % i 0: total i # 加入配对的因子但要避免重复加当i等于n/i时即n为完全平方数 j n // i if j ! i: total j return total def is_perfect_number(n): return get_sum_of_proper_divisors(n) n时间复杂度O(√n)。对于单个数的判断这已经足够高效。与质数的关联完数的寻找特别是寻找更大的完数与梅森素数密切相关。欧几里得-欧拉定理指出一个偶数是完数当且仅当它可以写成 2^(p-1) * (2^p - 1) 的形式其中2^p - 1是梅森素数。因此寻找新的完数等价于寻找新的梅森素数。这揭示了数论中不同概念之间深刻的联系。3. 实战解题框架与代码实现掌握了核心算法我们来看如何将它们组装起来解决具体的ACM题目。题目通常不会直接问“这是质数吗”或“这是完数吗”而是将这些作为子问题。3.1 典型题目模式一区间质数统计题目描述给定区间[a, b]1 a b 10^7甚至更大求区间内质数的个数。难点如果对每个数单独用试除法必然超时。必须使用筛法。解题策略直接筛到b如果b很大比如10^9内存放不下整个is_prime数组。分段筛区间筛这是解决此类问题的标准方法。我们只需要筛出[2, √b]范围内的所有质数然后用这些质数去筛掉区间[a, b]内的合数。代码实现def count_primes_in_range(a, b): 返回区间[a, b]内质数的数量。假设b可以很大但b-a在可接受范围如1e6内。 if a 2: a 2 if b a: return 0 limit int(math.isqrt(b)) # 第一步用埃氏筛筛出[2, limit]内的所有质数 is_prime_small [True] * (limit 1) is_prime_small[0] is_prime_small[1] False small_primes [] for i in range(2, limit 1): if is_prime_small[i]: small_primes.append(i) for j in range(i * i, limit 1, i): is_prime_small[j] False # 第二步用筛出的小质数筛掉区间[a, b]内的合数 is_prime_range [True] * (b - a 1) # 偏移数组is_prime_range[i] 对应数字 ai for p in small_primes: # 找到大于等于a的第一个p的倍数 start max(p * p, ((a p - 1) // p) * p) # 注意start可能超过int范围计算时小心 for j in range(start, b 1, p): is_prime_range[j - a] False # 统计质数个数 count 0 for i in range(len(is_prime_range)): if is_prime_range[i] and (a i) 2: # 确保数字2 count 1 return count实操要点start max(p * p, ((a p - 1) // p) * p)这行是关键。(a p - 1) // p是向上取整的整数除法得到ceil(a / p)。乘以p后就是大于等于a的第一个p的倍数。同时和埃氏筛一样我们从p*p开始标记避免重复。使用偏移数组is_prime_range来代表区间[a, b]节省内存。时间复杂度约为 O((b-a) log log b √b log log √b)在区间长度(b-a)可控时非常高效。3.2 典型题目模式二完数判断与枚举题目描述给定一个上限N找出所有不超过N的完数。已知数学事实偶完数与梅森素数一一对应。在已知的范围内截至2023年共发现51个梅森素数对应的完数也只有51个。对于竞赛题N通常不会超过10^8在这个范围内只有少数几个完数6, 28, 496, 8128, 33550336等。解题策略打表法由于完数极其稀少最实用的方法就是预先计算已知的完数然后根据输入的N进行匹配输出。这是竞赛中最常见的做法。直接计算法如果题目非要你算可以结合梅森素数来生成。即枚举p判断M_p 2^p - 1是否为素数用Miller-Rabin如果是则 2^(p-1) * M_p 就是一个偶完数。打表法示例KNOWN_PERFECT_NUMBERS [6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128] # 注意大数可能超出语言整型范围 def find_perfect_numbers_up_to(N): result [] for num in KNOWN_PERFECT_NUMBERS: if num N: result.append(num) else: break return result直接计算法示例用于理解原理def generate_even_perfect_numbers(limit_p31): # 只尝试较小的p perfects [] for p in [2, 3, 5, 7, 13, 17, 19, 31]: # 已知的梅森素数指数 mersenne (1 p) - 1 # 2^p - 1 if miller_rabin(mersenne): # 确认是质数 perfect (1 (p - 1)) * mersenne if perfect (1 63): # 限制在64位有符号整数范围内 perfects.append(perfect) return perfects注意奇完数是否存在是数论中著名的未解难题。因此目前所有已知的完数都是偶数且与梅森素数对应。题目中默认的完数也都是指偶完数。3.3 综合应用基于质因数分解求因子和有些题目变体不是直接问完数而是问一个数的所有因子之和或者“盈数”因子和大于自身、“亏数”因子和小于自身的分类。这时直接枚举到√n求因子和的方法get_sum_of_proper_divisors函数是可行的。但如果要对多个数进行这样的操作或者n本身很大我们需要更高效的方法。利用质因数分解求因子和公式 如果n的质因数分解为 n p1^a1 * p2^a2 * ... * pk^ak那么n的所有正因子之和为 σ(n) (1 p1 p1^2 ... p1^a1) * (1 p2 p2^2 ... p2^a2) * ... * (1 pk pk^2 ... pk^ak)真因子和 s(n) σ(n) - n。优势一旦得到质因数分解计算因子和就是O(k)的事情k是不同质因子的个数通常很小。关键在于如何快速分解。结合欧拉筛预处理最小质因子 我们可以在筛质数的同时记录每个数的最小质因子lpf。这样对于任意数n我们可以通过不断除以它的最小质因子来快速分解。def euler_sieve_with_lpf(n): 欧拉筛同时返回质数列表和最小质因子数组lpf。lpf[i]表示i的最小质因子lpf[i]0表示i是质数或0/1。 lpf [0] * (n 1) primes [] for i in range(2, n 1): if lpf[i] 0: # i是质数 lpf[i] i primes.append(i) for p in primes: if i * p n: break lpf[i * p] p if i % p 0: break return primes, lpf def factorize_using_lpf(x, lpf): 利用最小质因子数组lpf快速分解x。返回质因数列表格式为[(p1, a1), (p2, a2), ...] factors [] while x 1: p lpf[x] cnt 0 while x % p 0: x // p cnt 1 factors.append((p, cnt)) return factors def sum_of_divisors_from_factors(factors): 根据质因数分解列表factors计算所有正因子之和。 total 1 for p, a in factors: # 计算 (1 p p^2 ... p^a) # 等比数列求和公式 (p^(a1) - 1) / (p - 1) sum_pow (pow(p, a 1) - 1) // (p - 1) total * sum_pow return total应用场景如果题目需要频繁查询多个数的因子和比如求1到N每个数的因子和我们可以先用欧拉筛预处理出1到N的lpf数组然后对每个数进行快速分解和计算总复杂度接近O(N log N)比直接对每个数O(√N)枚举要快得多。4. 常见陷阱、优化技巧与问题排查在实际编码和调试过程中我积累了一些容易踩坑的地方和对应的优化技巧。4.1 性能陷阱与优化平方根计算的精度与性能问题在试除法和枚举因子时常用int(n**0.5)或int(math.sqrt(n))来计算上限。对于大整数nn**0.5是浮点数运算可能有精度误差例如对于完全平方数nn**0.5的结果可能略小于真实平方根取整后导致少检查一个数。解决使用int(math.isqrt(n))Python 3.8或自己实现整数平方根函数。math.isqrt是专门用于整数平方根的精确且高效。# 推荐 limit math.isqrt(n) # 旧版本Python替代方案 def integer_sqrt(x): r int(math.sqrt(x)) while (r 1) ** 2 x: r 1 while r ** 2 x: r - 1 return r循环边界与步长问题在优化试除法中循环写成for i in range(3, int(math.sqrt(n)) 1):。这里sqrt(n)返回浮点数1后再转int是安全的。但更优雅的是用isqrt。优化处理偶数后从3开始以步长2循环只检查奇数因子。关键点务必注意循环的上限是limit 1因为range是左闭右开区间。筛法的内存与速度权衡问题埃氏筛用bool数组Python中list of bool标记内存占用较大。当n接近10^8时内存可能达到几百MB。优化使用bytearray或array(b)比list更省内存。位筛法用一个比特位表示一个数的状态奇偶性可进一步压缩能将内存压缩到原来的1/8甚至更少。这是竞赛中的高级技巧。# 简单的位筛思想仅标记奇数 def bit_sieve(n): if n 2: return [] # 假设每个字节的bit表示连续的奇数1,3,5,7,... 对应bit0,bit1,bit2,bit3... size (n // 2) 1 sieve bytearray(b\x01) * size sieve[0] 0 # 1不是质数 limit int(math.isqrt(n)) for i in range(1, (limit // 2) 1): if sieve[i]: # 对应数字 p 2*i 1 是质数 p 2 * i 1 start (p * p) // 2 # 计算p*p在sieve中的索引 step p for j in range(start, size, step): sieve[j] 0 primes [2] primes.extend(2*i1 for i in range(1, size) if sieve[i]) return primes4.2 逻辑错误排查特殊值处理0和1它们既不是质数也不是合数。任何质数判断函数开头都必须检查n 2。负数根据题目定义通常质数和完数只针对正整数。函数应能处理或明确说明。大整数在Python中整数无溢出但在C/Java中要小心中间结果如i * i可能溢出需要使用long long类型。完数判断中的差一错误问题计算真因子和时容易错误地把自身n也加进去或者漏加因子1。检查用已知完数6, 28测试你的函数。get_sum_of_proper_divisors(6)必须返回6get_sum_of_proper_divisors(28)必须返回28。筛法中的索引错误埃氏筛内层循环for j in range(i*i, n1, i)要确保i*i不会溢出且在Python中range的终点是n1才能包含n。欧拉筛最易错的是if i % p 0: break这一句。忘记break会导致线性筛退化为近似O(n log n)的复杂度在大数据量时时间暴增。区间筛偏移数组is_prime_range[j-a]的下标计算要仔细验证。特别是当a和b很大时j-a可能为负要确保j从正确的start开始。4.3 调试与测试策略构造测试用例质数测试2最小的质数、3奇数质数、大质数如1000000007一个常用的模数。合数测试完全平方数如925、两个大质数乘积如101*103、包含小质因子的数。边界值测试01负数以及函数声明支持的最大值。完数测试6284968128。同时测试非完数如12盈数14亏数。对拍 写一个暴力但正确的算法例如对于质数判断用最朴素的O(n)算法对小数据验证与你的优化算法进行大量随机数据对比确保结果一致。这是竞赛中验证算法正确性的黄金方法。性能 profiling 对于大数据量使用Python的time模块或cProfile来测量函数运行时间确保符合预期复杂度。例如埃氏筛筛100万以内的质数应该在毫秒级完成。5. 从理论到实战一道综合题解让我们用一道虚构但典型的ACM风格题目来串联所有知识点题目给定两个整数L, R (1 ≤ L ≤ R ≤ 10^12, R-L ≤ 10^6)求区间[L, R]内有多少个“特殊数”。特殊数定义是它本身不是质数但其所有真因子之和是质数。思路拆解问题转化对于区间[L, R]内的每个数x我们需要 a. 判断x是否为质数不是则继续。 b. 计算x的所有真因子之和s。 c. 判断s是否为质数。性能瓶颈R最大10^12无法直接筛。但区间长度只有10^6提示使用区间筛。因子和计算对每个数枚举因子到√x最坏情况单个数需要10^6次操作区间10^6个数就是10^12超时。必须优化。优化策略利用区间筛的思想我们不仅能筛出合数还能记录每个数被哪些质数整除从而进行质因数分解再利用公式计算因子和。先用埃氏筛筛出[2, √R]内的所有质数。创建一个数组sum_div长度为R-L1初始值设为1因为1是每个数的因子。对于每个小质数p在区间[L, R]内标记其倍数。但不同于普通筛法只标记布尔值我们同时更新这个倍数对应的sum_div值。具体来说对于每个倍数m我们找出m中包含p的最高次幂然后应用因子和公式的增量更新。但这样实现复杂。更实际的方案由于区间长度只有10^6我们可以对区间内每个数用预处理的小质数表进行试除分解。因为任何数n的大于√n的质因子最多只有一个。所以我们用√R以内的小质数去试除每个数分解后如果剩余部分1则它是一个大质因子。预处理primes [2到√R的质数]。对于x从L到Rtemp x,sum 1遍历primes中每个p只要p*p temp如果temp % p 0计算p的幂次a并累乘sum * (p^(a1)-1)/(p-1)同时temp // p^a。循环后如果temp 1说明temp是一个质因子且大于√xsum * (temp^2 - 1)/(temp - 1) temp 1。得到因子总和σ(x)真因子和s σ(x) - x。判断x不是质数可以用区间筛的布尔数组判断且s是质数s可能很大需要用Miller-Rabin判断。判断质数x是否为质数在区间筛的过程中我们已经得到了一个布尔数组is_prime_range直接查表即可O(1)。s是否为质数s的范围可能很大最大约为x本身的数量级即10^12。需要用Miller-Rabin测试。因为10^12 2^64我们可以用一组确定的底数实现确定性的Miller-Rabin测试。核心代码框架import math import random def sieve_small(limit): 筛出[2, limit]内的质数 is_prime [True] * (limit 1) primes [] for i in range(2, limit 1): if is_prime[i]: primes.append(i) if i * i limit: for j in range(i * i, limit 1, i): is_prime[j] False return primes def miller_rabin_deterministic(n): 针对64位整数内的确定性Miller-Rabin测试 if n 2: return False small_primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for p in small_primes: if n % p 0: return n p d n - 1 s 0 while d % 2 0: d // 2 s 1 # 对于 2^64以下一组底数足以给出确定性结果 for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]: if a % n 0: continue x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x (x * x) % n if x n - 1: break else: return False return True def sum_of_divisors_from_prime_factors(x, primes): 利用预处理的质数表primes对x进行质因数分解并计算所有正因子之和。primes包含所有sqrt(x)的质数。 original_x x total 1 for p in primes: if p * p x: break if x % p 0: cnt 0 while x % p 0: x // p cnt 1 # 计算 (p^(cnt1) - 1) / (p - 1) total * (pow(p, cnt 1) - 1) // (p - 1) if x 1: # 剩余一个大于sqrt(original_x)的质因子 total * (x 1) # 因为 (x^2 -1)/(x-1) x1 return total def count_special_numbers(L, R): if L 2: L 2 if R L: return 0 # 步骤1区间筛标记[L, R]内的合数 limit int(math.isqrt(R)) small_primes sieve_small(limit) is_prime_range [True] * (R - L 1) # 处理L1的情况但上面已经调整L2 for p in small_primes: start max(p * p, ((L p - 1) // p) * p) for j in range(start, R 1, p): is_prime_range[j - L] False # 0和1不是质数但我们的L2所以不需要特别处理 # 步骤2预处理用于分解的小质数表就是small_primes # 步骤3遍历区间内的每个数 special_count 0 for x in range(L, R 1): idx x - L # 条件a: x本身不是质数 if is_prime_range[idx]: continue # x是质数跳过 # 条件bc: 计算真因子和s并判断s是否为质数 sigma_x sum_of_divisors_from_prime_factors(x, small_primes) s sigma_x - x if s 2 and miller_rabin_deterministic(s): special_count 1 return special_count # 示例使用 L, R 100, 200 print(f区间[{L}, {R}]内的特殊数个数为: {count_special_numbers(L, R)})这道题综合运用了区间筛法标记区间内质数。利用小质数表进行质因数分解。质因数分解公式计算因子和。Miller-Rabin素性测试判断大数是否为质数。通过这样的综合练习你就能深刻理解质数和因子相关算法是如何在复杂问题中协同工作的。记住在竞赛中清晰的思路和正确的工具选择往往比单纯的编码能力更重要。多练习多总结把这些模块内化成自己的本能反应。 质数筛法与完数判断：ACM数论算法实战优化指南
1. 项目概述从“完数难题”看质数模块的实战价值最近在整理ACM的解题笔记翻到Day7的质数与完数专题发现不少朋友对这两个看似基础的概念在实际编程题中的应用感到头疼。尤其是当题目要求处理大范围数据或者将质数性质与“完数”这类特殊数结合时很多人的第一反应就是暴力循环结果不是超时就是内存溢出。我自己在早期刷题时也踩过不少坑比如试图用最朴素的试除法去筛一千万以内的素数结果程序直接卡死。今天我就结合“完数难题”这个具体的切入点把质数素数模块的核心算法、优化技巧以及它们如何应用于解决复杂问题系统地梳理一遍。无论你是正在备战ACM的新手还是想巩固数论基础的开发者相信这篇从实战出发的总结都能给你带来直接的帮助。所谓“完数”又称完全数是指一个数恰好等于它所有真因子即除了自身以外的正因子之和。比如612328124714。而质数则是只有1和它本身两个正因子的数。这两者看似独立但在算法题中常常被结合起来考察例如判断一个数是否为完数就需要高效找出其所有真因子这其中就涉及到因式分解而质数判断与筛法是高效分解的基础。我们今天的讨论将不止步于概念而是深入到代码实现、性能优化和解题策略中。2. 核心算法原理与选型逻辑在解决涉及质数和完数的ACM题目时算法选型直接决定了程序的生死。下面我们拆解几个核心算法并解释为什么在特定场景下要这么选。2.1 质数判断从试除法到Miller-Rabin最基础的质数判断问题是给定一个整数n判断它是否为质数。1. 朴素试除法这是最直观的想法用2到n-1的每个数去试除n如果都不能整除n就是质数。时间复杂度O(n)。def is_prime_naive(n): if n 2: return False for i in range(2, n): # 从2遍历到n-1 if n % i 0: return False return True注意这种方法仅适用于教学和理解概念对于n稍大比如超过10^5的情况就完全不可用。2. 优化试除法一个关键的数学优化如果n是一个合数那么它必定有一个不大于√n的质因子。因此我们只需要试除到√n即可。时间复杂度降为O(√n)。import math def is_prime_optimized(n): if n 2: return False # 单独处理偶数加速 if n % 2 0: return n 2 # 从3开始步长为2只检查奇数 limit int(math.isqrt(n)) # Python 3.8 使用 isqrt 获取整数平方根 for i in range(3, limit 1, 2): if n % i 0: return False return True为什么有效假设n a * b且a ≤ b。那么a ≤ √n。只要检查完所有≤√n的数就足以判断n是否为合数。单独处理偶数和步长为2的循环是基于“除了2以外所有质数都是奇数”的事实能减少近一半的循环次数。3. Miller-Rabin素性测试当n非常大比如超过10^14时O(√n)的复杂度依然太高。这时需要概率性算法Miller-Rabin是最常用的一种。它是一个多项式时间算法基于费马小定理和二次探测定理。虽然理论上是概率算法但通过选择特定的底数集合对于一定范围内的整数如小于2^64可以做到确定性判断。def miller_rabin(n, k5): # k为测试轮数增加可提高准确性 if n 2: return False for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]: if n % p 0: return n p d n - 1 s 0 while d % 2 0: d // 2 s 1 for _ in range(k): a random.randrange(2, n - 1) x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x (x * x) % n if x n - 1: break else: return False return True选型逻辑n 10^6使用优化试除法代码简单结果绝对正确。10^6 n 10^12可以考虑用预处理的小质数表如前1000个质数先试除再用优化试除法能过滤掉大部分合数。n 10^12或需要极高性能使用Miller-Rabin素性测试。在ACM竞赛中对于64位整数范围内的确定性判断通常使用固定的一组底数如[2, 325, 9375, 28178, 450775, 9780504, 1795265022]即可。2.2 质数筛法埃氏筛与欧拉筛当题目要求找出某一范围内如1到n的所有质数时逐个判断的效率太低需要使用筛法。1. 埃拉托斯特尼筛法埃氏筛核心思想从2开始将每个质数的倍数标记为合数。def sieve_of_eratosthenes(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: # 从i*i开始标记因为i*(i-1)等已被更小的质数标记过 for j in range(i * i, n 1, i): is_prime[j] False primes [i for i in range(2, n1) if is_prime[i]] return primes时间复杂度O(n log log n)。空间复杂度O(n)。为什么从i*i开始对于当前质数i比ii小的合数ikki一定已经被更小的质数比如k的质因子标记过了。这是一个重要的优化点能减少重复标记。2. 欧拉筛线性筛埃氏筛的一个问题是有些合数会被多个质数重复标记如6会被2和3都标记。欧拉筛保证了每个合数只被其最小质因子标记一次从而达到线性时间复杂度O(n)。def euler_sieve(n): is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) for p in primes: if i * p n: break is_prime[i * p] False if i % p 0: # 关键保证每个合数只被最小质因子筛掉 break return primes关键点解析if i % p 0: break这行代码是欧拉筛的灵魂。当p能整除i时说明p是i的最小质因子因为primes是递增的。那么对于后续更大的质数pi * p的最小质因子应该是p而不是p所以应该留到后面当i增长到某个倍数时由p来筛掉现在不能筛否则就重复了。选型逻辑埃氏筛实现简单效率足够应对大部分题目n在10^7以内。在内存允许的情况下是首选。欧拉筛当n非常大接近10^7或更大且需要严格线性时间复杂度或者需要同步获取每个数的最小质因子用于后续快速因式分解时使用。欧拉筛稍复杂但性能更优。2.3 完数判断与因式分解判断一个数n是否为完数需要计算其所有真因子之和。最直接的方法是遍历1到n-1求和复杂度O(n)不可取。高效方法成对枚举因子。 性质如果d是n的因子那么n/d也是n的因子。我们只需要枚举到√n即可。def get_sum_of_proper_divisors(n): if n 1: return 0 total 1 # 1是所有大于1的数的因子 limit int(math.isqrt(n)) for i in range(2, limit 1): if n % i 0: total i # 加入配对的因子但要避免重复加当i等于n/i时即n为完全平方数 j n // i if j ! i: total j return total def is_perfect_number(n): return get_sum_of_proper_divisors(n) n时间复杂度O(√n)。对于单个数的判断这已经足够高效。与质数的关联完数的寻找特别是寻找更大的完数与梅森素数密切相关。欧几里得-欧拉定理指出一个偶数是完数当且仅当它可以写成 2^(p-1) * (2^p - 1) 的形式其中2^p - 1是梅森素数。因此寻找新的完数等价于寻找新的梅森素数。这揭示了数论中不同概念之间深刻的联系。3. 实战解题框架与代码实现掌握了核心算法我们来看如何将它们组装起来解决具体的ACM题目。题目通常不会直接问“这是质数吗”或“这是完数吗”而是将这些作为子问题。3.1 典型题目模式一区间质数统计题目描述给定区间[a, b]1 a b 10^7甚至更大求区间内质数的个数。难点如果对每个数单独用试除法必然超时。必须使用筛法。解题策略直接筛到b如果b很大比如10^9内存放不下整个is_prime数组。分段筛区间筛这是解决此类问题的标准方法。我们只需要筛出[2, √b]范围内的所有质数然后用这些质数去筛掉区间[a, b]内的合数。代码实现def count_primes_in_range(a, b): 返回区间[a, b]内质数的数量。假设b可以很大但b-a在可接受范围如1e6内。 if a 2: a 2 if b a: return 0 limit int(math.isqrt(b)) # 第一步用埃氏筛筛出[2, limit]内的所有质数 is_prime_small [True] * (limit 1) is_prime_small[0] is_prime_small[1] False small_primes [] for i in range(2, limit 1): if is_prime_small[i]: small_primes.append(i) for j in range(i * i, limit 1, i): is_prime_small[j] False # 第二步用筛出的小质数筛掉区间[a, b]内的合数 is_prime_range [True] * (b - a 1) # 偏移数组is_prime_range[i] 对应数字 ai for p in small_primes: # 找到大于等于a的第一个p的倍数 start max(p * p, ((a p - 1) // p) * p) # 注意start可能超过int范围计算时小心 for j in range(start, b 1, p): is_prime_range[j - a] False # 统计质数个数 count 0 for i in range(len(is_prime_range)): if is_prime_range[i] and (a i) 2: # 确保数字2 count 1 return count实操要点start max(p * p, ((a p - 1) // p) * p)这行是关键。(a p - 1) // p是向上取整的整数除法得到ceil(a / p)。乘以p后就是大于等于a的第一个p的倍数。同时和埃氏筛一样我们从p*p开始标记避免重复。使用偏移数组is_prime_range来代表区间[a, b]节省内存。时间复杂度约为 O((b-a) log log b √b log log √b)在区间长度(b-a)可控时非常高效。3.2 典型题目模式二完数判断与枚举题目描述给定一个上限N找出所有不超过N的完数。已知数学事实偶完数与梅森素数一一对应。在已知的范围内截至2023年共发现51个梅森素数对应的完数也只有51个。对于竞赛题N通常不会超过10^8在这个范围内只有少数几个完数6, 28, 496, 8128, 33550336等。解题策略打表法由于完数极其稀少最实用的方法就是预先计算已知的完数然后根据输入的N进行匹配输出。这是竞赛中最常见的做法。直接计算法如果题目非要你算可以结合梅森素数来生成。即枚举p判断M_p 2^p - 1是否为素数用Miller-Rabin如果是则 2^(p-1) * M_p 就是一个偶完数。打表法示例KNOWN_PERFECT_NUMBERS [6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128] # 注意大数可能超出语言整型范围 def find_perfect_numbers_up_to(N): result [] for num in KNOWN_PERFECT_NUMBERS: if num N: result.append(num) else: break return result直接计算法示例用于理解原理def generate_even_perfect_numbers(limit_p31): # 只尝试较小的p perfects [] for p in [2, 3, 5, 7, 13, 17, 19, 31]: # 已知的梅森素数指数 mersenne (1 p) - 1 # 2^p - 1 if miller_rabin(mersenne): # 确认是质数 perfect (1 (p - 1)) * mersenne if perfect (1 63): # 限制在64位有符号整数范围内 perfects.append(perfect) return perfects注意奇完数是否存在是数论中著名的未解难题。因此目前所有已知的完数都是偶数且与梅森素数对应。题目中默认的完数也都是指偶完数。3.3 综合应用基于质因数分解求因子和有些题目变体不是直接问完数而是问一个数的所有因子之和或者“盈数”因子和大于自身、“亏数”因子和小于自身的分类。这时直接枚举到√n求因子和的方法get_sum_of_proper_divisors函数是可行的。但如果要对多个数进行这样的操作或者n本身很大我们需要更高效的方法。利用质因数分解求因子和公式 如果n的质因数分解为 n p1^a1 * p2^a2 * ... * pk^ak那么n的所有正因子之和为 σ(n) (1 p1 p1^2 ... p1^a1) * (1 p2 p2^2 ... p2^a2) * ... * (1 pk pk^2 ... pk^ak)真因子和 s(n) σ(n) - n。优势一旦得到质因数分解计算因子和就是O(k)的事情k是不同质因子的个数通常很小。关键在于如何快速分解。结合欧拉筛预处理最小质因子 我们可以在筛质数的同时记录每个数的最小质因子lpf。这样对于任意数n我们可以通过不断除以它的最小质因子来快速分解。def euler_sieve_with_lpf(n): 欧拉筛同时返回质数列表和最小质因子数组lpf。lpf[i]表示i的最小质因子lpf[i]0表示i是质数或0/1。 lpf [0] * (n 1) primes [] for i in range(2, n 1): if lpf[i] 0: # i是质数 lpf[i] i primes.append(i) for p in primes: if i * p n: break lpf[i * p] p if i % p 0: break return primes, lpf def factorize_using_lpf(x, lpf): 利用最小质因子数组lpf快速分解x。返回质因数列表格式为[(p1, a1), (p2, a2), ...] factors [] while x 1: p lpf[x] cnt 0 while x % p 0: x // p cnt 1 factors.append((p, cnt)) return factors def sum_of_divisors_from_factors(factors): 根据质因数分解列表factors计算所有正因子之和。 total 1 for p, a in factors: # 计算 (1 p p^2 ... p^a) # 等比数列求和公式 (p^(a1) - 1) / (p - 1) sum_pow (pow(p, a 1) - 1) // (p - 1) total * sum_pow return total应用场景如果题目需要频繁查询多个数的因子和比如求1到N每个数的因子和我们可以先用欧拉筛预处理出1到N的lpf数组然后对每个数进行快速分解和计算总复杂度接近O(N log N)比直接对每个数O(√N)枚举要快得多。4. 常见陷阱、优化技巧与问题排查在实际编码和调试过程中我积累了一些容易踩坑的地方和对应的优化技巧。4.1 性能陷阱与优化平方根计算的精度与性能问题在试除法和枚举因子时常用int(n**0.5)或int(math.sqrt(n))来计算上限。对于大整数nn**0.5是浮点数运算可能有精度误差例如对于完全平方数nn**0.5的结果可能略小于真实平方根取整后导致少检查一个数。解决使用int(math.isqrt(n))Python 3.8或自己实现整数平方根函数。math.isqrt是专门用于整数平方根的精确且高效。# 推荐 limit math.isqrt(n) # 旧版本Python替代方案 def integer_sqrt(x): r int(math.sqrt(x)) while (r 1) ** 2 x: r 1 while r ** 2 x: r - 1 return r循环边界与步长问题在优化试除法中循环写成for i in range(3, int(math.sqrt(n)) 1):。这里sqrt(n)返回浮点数1后再转int是安全的。但更优雅的是用isqrt。优化处理偶数后从3开始以步长2循环只检查奇数因子。关键点务必注意循环的上限是limit 1因为range是左闭右开区间。筛法的内存与速度权衡问题埃氏筛用bool数组Python中list of bool标记内存占用较大。当n接近10^8时内存可能达到几百MB。优化使用bytearray或array(b)比list更省内存。位筛法用一个比特位表示一个数的状态奇偶性可进一步压缩能将内存压缩到原来的1/8甚至更少。这是竞赛中的高级技巧。# 简单的位筛思想仅标记奇数 def bit_sieve(n): if n 2: return [] # 假设每个字节的bit表示连续的奇数1,3,5,7,... 对应bit0,bit1,bit2,bit3... size (n // 2) 1 sieve bytearray(b\x01) * size sieve[0] 0 # 1不是质数 limit int(math.isqrt(n)) for i in range(1, (limit // 2) 1): if sieve[i]: # 对应数字 p 2*i 1 是质数 p 2 * i 1 start (p * p) // 2 # 计算p*p在sieve中的索引 step p for j in range(start, size, step): sieve[j] 0 primes [2] primes.extend(2*i1 for i in range(1, size) if sieve[i]) return primes4.2 逻辑错误排查特殊值处理0和1它们既不是质数也不是合数。任何质数判断函数开头都必须检查n 2。负数根据题目定义通常质数和完数只针对正整数。函数应能处理或明确说明。大整数在Python中整数无溢出但在C/Java中要小心中间结果如i * i可能溢出需要使用long long类型。完数判断中的差一错误问题计算真因子和时容易错误地把自身n也加进去或者漏加因子1。检查用已知完数6, 28测试你的函数。get_sum_of_proper_divisors(6)必须返回6get_sum_of_proper_divisors(28)必须返回28。筛法中的索引错误埃氏筛内层循环for j in range(i*i, n1, i)要确保i*i不会溢出且在Python中range的终点是n1才能包含n。欧拉筛最易错的是if i % p 0: break这一句。忘记break会导致线性筛退化为近似O(n log n)的复杂度在大数据量时时间暴增。区间筛偏移数组is_prime_range[j-a]的下标计算要仔细验证。特别是当a和b很大时j-a可能为负要确保j从正确的start开始。4.3 调试与测试策略构造测试用例质数测试2最小的质数、3奇数质数、大质数如1000000007一个常用的模数。合数测试完全平方数如925、两个大质数乘积如101*103、包含小质因子的数。边界值测试01负数以及函数声明支持的最大值。完数测试6284968128。同时测试非完数如12盈数14亏数。对拍 写一个暴力但正确的算法例如对于质数判断用最朴素的O(n)算法对小数据验证与你的优化算法进行大量随机数据对比确保结果一致。这是竞赛中验证算法正确性的黄金方法。性能 profiling 对于大数据量使用Python的time模块或cProfile来测量函数运行时间确保符合预期复杂度。例如埃氏筛筛100万以内的质数应该在毫秒级完成。5. 从理论到实战一道综合题解让我们用一道虚构但典型的ACM风格题目来串联所有知识点题目给定两个整数L, R (1 ≤ L ≤ R ≤ 10^12, R-L ≤ 10^6)求区间[L, R]内有多少个“特殊数”。特殊数定义是它本身不是质数但其所有真因子之和是质数。思路拆解问题转化对于区间[L, R]内的每个数x我们需要 a. 判断x是否为质数不是则继续。 b. 计算x的所有真因子之和s。 c. 判断s是否为质数。性能瓶颈R最大10^12无法直接筛。但区间长度只有10^6提示使用区间筛。因子和计算对每个数枚举因子到√x最坏情况单个数需要10^6次操作区间10^6个数就是10^12超时。必须优化。优化策略利用区间筛的思想我们不仅能筛出合数还能记录每个数被哪些质数整除从而进行质因数分解再利用公式计算因子和。先用埃氏筛筛出[2, √R]内的所有质数。创建一个数组sum_div长度为R-L1初始值设为1因为1是每个数的因子。对于每个小质数p在区间[L, R]内标记其倍数。但不同于普通筛法只标记布尔值我们同时更新这个倍数对应的sum_div值。具体来说对于每个倍数m我们找出m中包含p的最高次幂然后应用因子和公式的增量更新。但这样实现复杂。更实际的方案由于区间长度只有10^6我们可以对区间内每个数用预处理的小质数表进行试除分解。因为任何数n的大于√n的质因子最多只有一个。所以我们用√R以内的小质数去试除每个数分解后如果剩余部分1则它是一个大质因子。预处理primes [2到√R的质数]。对于x从L到Rtemp x,sum 1遍历primes中每个p只要p*p temp如果temp % p 0计算p的幂次a并累乘sum * (p^(a1)-1)/(p-1)同时temp // p^a。循环后如果temp 1说明temp是一个质因子且大于√xsum * (temp^2 - 1)/(temp - 1) temp 1。得到因子总和σ(x)真因子和s σ(x) - x。判断x不是质数可以用区间筛的布尔数组判断且s是质数s可能很大需要用Miller-Rabin判断。判断质数x是否为质数在区间筛的过程中我们已经得到了一个布尔数组is_prime_range直接查表即可O(1)。s是否为质数s的范围可能很大最大约为x本身的数量级即10^12。需要用Miller-Rabin测试。因为10^12 2^64我们可以用一组确定的底数实现确定性的Miller-Rabin测试。核心代码框架import math import random def sieve_small(limit): 筛出[2, limit]内的质数 is_prime [True] * (limit 1) primes [] for i in range(2, limit 1): if is_prime[i]: primes.append(i) if i * i limit: for j in range(i * i, limit 1, i): is_prime[j] False return primes def miller_rabin_deterministic(n): 针对64位整数内的确定性Miller-Rabin测试 if n 2: return False small_primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for p in small_primes: if n % p 0: return n p d n - 1 s 0 while d % 2 0: d // 2 s 1 # 对于 2^64以下一组底数足以给出确定性结果 for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]: if a % n 0: continue x pow(a, d, n) if x 1 or x n - 1: continue for _ in range(s - 1): x (x * x) % n if x n - 1: break else: return False return True def sum_of_divisors_from_prime_factors(x, primes): 利用预处理的质数表primes对x进行质因数分解并计算所有正因子之和。primes包含所有sqrt(x)的质数。 original_x x total 1 for p in primes: if p * p x: break if x % p 0: cnt 0 while x % p 0: x // p cnt 1 # 计算 (p^(cnt1) - 1) / (p - 1) total * (pow(p, cnt 1) - 1) // (p - 1) if x 1: # 剩余一个大于sqrt(original_x)的质因子 total * (x 1) # 因为 (x^2 -1)/(x-1) x1 return total def count_special_numbers(L, R): if L 2: L 2 if R L: return 0 # 步骤1区间筛标记[L, R]内的合数 limit int(math.isqrt(R)) small_primes sieve_small(limit) is_prime_range [True] * (R - L 1) # 处理L1的情况但上面已经调整L2 for p in small_primes: start max(p * p, ((L p - 1) // p) * p) for j in range(start, R 1, p): is_prime_range[j - L] False # 0和1不是质数但我们的L2所以不需要特别处理 # 步骤2预处理用于分解的小质数表就是small_primes # 步骤3遍历区间内的每个数 special_count 0 for x in range(L, R 1): idx x - L # 条件a: x本身不是质数 if is_prime_range[idx]: continue # x是质数跳过 # 条件bc: 计算真因子和s并判断s是否为质数 sigma_x sum_of_divisors_from_prime_factors(x, small_primes) s sigma_x - x if s 2 and miller_rabin_deterministic(s): special_count 1 return special_count # 示例使用 L, R 100, 200 print(f区间[{L}, {R}]内的特殊数个数为: {count_special_numbers(L, R)})这道题综合运用了区间筛法标记区间内质数。利用小质数表进行质因数分解。质因数分解公式计算因子和。Miller-Rabin素性测试判断大数是否为质数。通过这样的综合练习你就能深刻理解质数和因子相关算法是如何在复杂问题中协同工作的。记住在竞赛中清晰的思路和正确的工具选择往往比单纯的编码能力更重要。多练习多总结把这些模块内化成自己的本能反应。