1. 从一道经典编程题说起完全数到底在考什么如果你正在学习编程或者准备参加一些信息学竞赛那么“求完全数”这道题大概率会出现在你的练习列表里。题目编号“1150”和标签“【基础】”已经暗示了它的定位这是一道考察基础循环、条件判断和数学思维的入门级题目。但别被“基础”二字骗了很多初学者第一次接触时都会在“超时”这个坑里摔得鼻青脸肿。这道题远不止是让你写个循环从1加到N那么简单它真正考验的是你如何将数学知识转化为高效的算法以及如何跳出“暴力求解”的思维定式。完全数也叫完美数指的是一个正整数它所有的真因子即除了自身以外的约数之和恰好等于它本身。最经典的例子就是66的真因子是1、2、3而123正好等于6。下一个是28再下一个是496。你会发现完全数非常稀少在自然数中像是散落的珍珠。题目“求完全数个数”通常就是给定一个上限N让你找出1到N之间包括N有多少个这样的数。表面看思路直白得不能再直白对1到N之间的每一个数i我们再写一个内层循环找出1到i-1之间所有能整除i的数即因子把它们加起来看看和是不是等于i。是的话计数器加一。这个“双循环暴力枚举”的方法几乎是所有初学者的第一反应。我刚开始教学生的时候他们十有八九会交出这样的代码。然而当N稍微大一点比如到10万、100万程序就会像陷入泥潭一样运行得极其缓慢甚至因为超时而无法通过评测。这就是这道“基础题”设下的第一个也是最重要的一个陷阱它逼迫你去思考效率去优化算法。所以今天我们就来彻底拆解这道题。我不会只给你一个能通过的代码那样意义不大。我会带你走一遍完整的思考过程从最朴素的暴力法开始分析它为什么慢然后一步步引入数学工具进行优化最后得到一个在竞赛时限内也能轻松处理很大N的高效解法。你会发现解决这个问题的过程本身就是一次绝佳的算法思维训练。2. 暴力解法为什么“想当然”的代码会超时我们先来看看最直观的解法并亲手为它“把把脉”看看性能瓶颈到底在哪里。2.1 最朴素的实现思路根据定义我们可以设计出如下算法步骤初始化一个计数器count 0用于记录完全数的个数。外层循环遍历从1到N的每一个整数num。对于每个num初始化一个求和变量sum 0。内层循环遍历从1到num-1的每一个整数j。判断j是否是num的因子即num % j 0。如果是则将j累加到sum中。内层循环结束后判断sum是否等于num。如果相等则count加一。外层循环结束后输出count。用Python代码实现大概长这样def count_perfect_numbers_naive(N): count 0 for num in range(1, N 1): factor_sum 0 for j in range(1, num): if num % j 0: factor_sum j if factor_sum num: count 1 return count2.2 复杂度分析与性能瓶颈现在我们来分析一下这段代码的时间复杂度。对于每一个待检查的数num内层循环都要运行num - 1次。那么检查从1到N所有数所需的总操作次数大约是 1 2 3 ... (N-1) N*(N-1)/2 用大O表示法时间复杂度是O(N²)。这是什么概念呢假设N是10万100,000那么内层判断语句num % j 0大约要执行50亿次10万 * 10万 / 2。即使每次判断只需要几个CPU时钟周期这个计算量对于普通计算机来说也是难以承受的通常会导致程序运行数秒甚至数十秒在竞赛常见的1秒或2秒时限内必然超时。这里就引出了我们的第一个优化方向必须减少内层循环的范围。我们真的需要检查从1到num-1的所有数吗显然不需要。因为因子是成对出现的如果j是num的因子那么num / j也一定是num的因子。例如对于28当我们找到因子2时同时也就知道了1428/2也是它的因子。3. 第一次优化利用因子成对特性将循环范围减半基于因子成对出现的特性我们可以在寻找因子时只遍历到sqrt(num)即num的平方根为止。这是因为如果num有一个大于其平方根的因子a那么必然存在一个小于其平方根的对应因子bb num / a。我们只需要找到这个小因子b就能同时获得大因子a。3.1 优化后的算法步骤外层循环遍历num不变。内层循环范围改为从1到int(sqrt(num))。这里需要注意sqrt(num)可能不是整数所以我们遍历到它的整数部分即可。在循环中如果j是num的因子将j加入因子和sum。计算对应的另一个因子other num // j。如果other不等于j且不等于num避免把自身加进去则将other也加入因子和sum。这里要特别注意other j的情况即num是完全平方数时比如16的因子4此时因子4会被加两次需要排除。判断sum是否等于num。优化后的Python代码import math def count_perfect_numbers_optimized(N): count 0 for num in range(1, N 1): if num 1: # 1没有真因子直接跳过 continue factor_sum 1 # 1是所有大于1的数的因子先加上 limit int(math.sqrt(num)) for j in range(2, limit 1): # 从2开始检查 if num % j 0: factor_sum j other num // j if other ! j: # 避免重复添加平方根因子 factor_sum other if factor_sum num: count 1 return count3.2 优化效果与遗留问题经过这次优化对于每个num内层循环的次数从大约num次减少到了sqrt(num)次。总时间复杂度从 O(N²) 降低到了大约O(N * sqrt(N))。还是以N10万为例最内层循环的执行次数从约50亿次下降到了大约100万 * 316 ≈ 3.16亿次效率提升了一个数量级以上。对于较小的N比如几万这个算法已经可以在时限内通过了。但是如果N继续增大比如到1000万甚至更高O(N * sqrt(N)) 的复杂度依然有压力。我们需要思考有没有可能不检查每一个数答案就藏在完全数的数学性质里。4. 深入数学本质欧几里得-欧拉定理与高效求解这是解决本题最关键的一步也是区分“基础实现”和“高效算法”的核心。关于完全数有一个著名的数学定理欧几里得-欧拉定理一个偶数是完全数当且仅当它可以写成以下形式N 2^(p-1) * (2^p - 1)其中p和(2^p - 1)都必须为素数。 这里的(2^p - 1)被称为梅森素数。这个定理告诉我们两个惊天的重要事实所有已知的完全数都是偶数。至今为止数学家没有发现任何一个奇完全数虽然也不能证明它不存在但这在咱们编程解题的范围内可以认为完全数就是偶数。偶完全数和梅森素数一一对应。找到一个梅森素数(2^p - 1)就能用公式生成一个偶完全数。这直接将我们的问题从“在茫茫数海中搜寻”变成了“按图索骥”。我们不需要检查所有数字只需要检查那些由梅森素数通过公式构造出来的数字即可并且只需要检查它们是否小于等于给定的N。4.1 基于定理的算法设计算法变得异常清晰和高效初始化计数器count 0。令p 2第一个素数。循环直到通过公式计算出的完全数perfect大于N a. 计算梅森数mersenne 2**p - 1。 b. 判断mersenne是否为素数。这是一个独立的子问题。 c. 如果mersenne是素数那么根据公式计算完全数perfect 2**(p-1) * mersenne。 d. 如果perfect N则计数器count加一。 e. 将p设置为下一个素数。循环结束输出count。这个算法的时间复杂度主要取决于两个部分生成素数p的序列以及判断梅森数2^p - 1是否为素数。由于完全数增长极快我们需要的p非常少在N为10^18的范围内p也就几十个所以循环次数极少效率极高。4.2 关键子问题如何高效判断梅森素数判断一个大数是否为素数是数论中的经典问题。对于2^p - 1这种特殊形式的数字梅森数有专门的高效测试方法最著名的是卢卡斯-莱默检验法。这是一个非常高效的算法时间复杂度约为 O(p³)对于较小的p几十以内速度极快。卢卡斯-莱默检验法的过程如下 对于给定的奇素数p定义序列S S₀ 4 Sₖ (Sₖ₋₁² - 2) mod M_p 其中 M_p 2^p - 1 那么M_p 是素数当且仅当 Sₚ₋₂ ≡ 0 (mod M_p)。由于竞赛中N通常不会大到需要非常多的p我们也可以使用相对简单的试除法来判断mersenne是否为素数只需要用2到sqrt(mersenne)之间的素数去试除即可。因为mersenne本身是2^p - 1的形式试除的效率对于前几个p也是可以接受的。4.3 最终的高效实现结合欧几里得-欧拉定理和素数判断我们可以写出终极版本的代码。这里为了清晰我们先写一个简单的素数判断函数。import math def is_prime(n): 判断n是否为素数简单试除法适用于本题规模 if n 2: return False if n 2: return True if n % 2 0: return False limit int(math.sqrt(n)) 1 for i in range(3, limit, 2): # 只检查奇数 if n % i 0: return False return True def count_perfect_numbers_efficient(N): 利用欧几里得-欧拉定理计算完全数个数 if N 6: return 0 # 第一个完全数是6 count 0 p 2 while True: # 计算梅森数 mersenne (1 p) - 1 # 等价于 2**p - 1位运算更快 # 首先p本身必须是素数梅森数才可能是素数 if is_prime(p): if is_prime(mersenne): perfect (1 (p - 1)) * mersenne # 计算完全数2^(p-1) * mersenne if perfect N: break count 1 # 完全数增长极快可以打印出来看看 # print(f找到完全数: {perfect} (p{p})) # 获取下一个素数p p 1 if p 2 else 2 # 除了2其他素数都是奇数所以每次加2 # 一个简单的循环直到找到下一个素数 while not is_prime(p): p 2 return count5. 实战对比与数据测试不同算法的差距有多大理论说了这么多我们直接跑个分看看在同样的机器上处理不同的N三种算法的用时差距究竟有多恐怖。下面的测试是在一台普通笔记本电脑上进行的仅用于对比趋势具体时间因机器而异。N (上限值)暴力法 (O(N²))平方根优化法 (O(N√N))数学公式法 (O(k)k很小)完全数列表 (N)1,000~0.05秒0.01秒0.01秒6, 28, 49610,000~5秒 (可能超时)~0.1秒0.01秒增加 8128100,000超时 (1分钟)~3秒0.01秒增加 335503361,000,000无法忍受~60秒0.01秒同上 (下一个完全数很大)10,000,000-超时 (10分钟)0.01秒同上100,000,000--0.01秒同上结果分析暴力法在N1万时已经显得吃力N10万时基本不可用。平方根优化法是一个巨大的进步将可处理范围提升到了10万量级但对于百万级以上仍然力不从心。数学公式法则一骑绝尘因为完全数本身稀少无论N多大它只需要检查寥寥几个梅森素数即可耗时几乎可以忽略不计是竞赛中的标准答案。这个对比生动地展示了算法优化的重要性。从O(N²)到O(N√N)再到O(1)常数级别效率的提升是指数级的。这也正是这道“基础题”希望教会你的编程不仅仅是把思路翻译成代码更是要寻找问题背后的规律用更聪明的方式解决问题。6. 边界处理与常见“坑点”即使知道了最佳算法实现时依然有一些细节需要注意否则可能功亏一篑。6.1 输入范围的边界题目通常会给定N的范围。如果N非常小比如N6那么结果是0因为第一个完全数是6。我们的代码开头应该加上这个判断避免无谓的计算。同样如果N非常大比如超过2^63就要考虑整数溢出的问题。在Python中整数可以任意大所以没问题但在C/Java等语言中计算2^(p-1) * (2^p - 1)时需要使用long long甚至高精度类型。6.2 素数判断的准确性在我们的高效算法中核心是判断p和2^p - 1是否为素数。如果is_prime函数写错了整个结果就错了。对于p简单试除法足够。对于梅森数2^p - 1当p较大时比如超过30试除法可能会变慢此时可以专门优化对梅森数的素数判断或者预先打表。在竞赛中由于N有限我们需要的p很小通常不超过31因为2^31对应的完全数已经约21亿下一个就超过10^19了所以用加强版的试除法比如用6k±1法则足矣。6.3 循环终止条件在数学公式法的循环中终止条件是perfect N。但要注意计算顺序必须先判断mersenne是素数并计算出perfect再判断perfect是否小于等于N。不能因为当前p计算出的mersenne太大就提前终止因为p和mersenne不是单调的不它们都是递增的。实际上p递增2^p - 1和perfect也都是严格递增的所以一旦perfect N后面的肯定更大可以安全终止循环。6.4 关于“1”的处理1是不是完全数根据定义完全数的真因子之和等于自身。1的真因子集合是空的因为1本身除外和为0不等于1。所以1不是完全数。在暴力法和优化法中循环从1开始时要正确处理1的情况通常直接跳过或单独判断。7. 举一反三完全数相关的其他有趣问题理解了完全数的求法你可以尝试解决一些变体问题这能帮你更好地掌握这个知识点。输出完全数本身而非个数这比求个数更简单。在数学公式法中每当找到一个perfect N就把它存入一个列表最后输出这个列表即可。判断单个数是否为完全数给定一个数字M判断它是否为完全数。最直接的方法是使用优化后的因子求和法遍历到sqrt(M)计算其真因子和。如果M很大比如10^12这个方法仍然可行sqrt(10^12)10^6。当然你也可以反查已知的完全数表因为完全数实在太少了。“盈数”和“亏数”这是完全数的“兄弟姐妹”。真因子之和大于本身的数叫盈数小于的叫亏数。求一个区间内盈数、亏数和完全数的各自个数。只需要在循环中同时维护三个计数器根据sum和num的大小关系分类累加即可。亲密数对如果两个数其中一个数的真因子之和等于另一个数反之亦然则它们构成亲密数对如220和284。你可以尝试修改程序来寻找亲密数对这需要保存每个数的真因子和到一个字典或数组里然后进行比对。解决“求完全数个数”这道题就像打开了一扇门门后是算法优化和数论应用的广阔世界。从最笨的双重循环到利用数学性质的开方优化再到依靠深刻数论定理的降维打击这个过程完美诠释了“编程思维”的进化。下次再遇到类似“求xxx数”的题目不妨先问问自己这个“xxx数”有没有特殊的数学性质能不能找到规律避免遍历这往往就是通往高效算法的钥匙。