从完全数问题入门算法优化：暴力枚举、因子求和与数论方法详解

1. 项目概述从一道经典编程题说起“求完全数的个数”这个标题对于任何一位有过编程入门经验的朋友来说都再熟悉不过了。它通常出现在各类编程竞赛、算法练习平台或者计算机专业的基础课程中编号“1150”和标签“【基础】”更是直接点明了它的定位——一道考察循环、条件判断和数学基础知识的入门级题目。乍一看这似乎只是一个简单的“暴力枚举”练习但如果你真的这么认为那可能就错过了这道题背后蕴含的丰富内涵和层层递进的优化思想。完全数又称完美数是一个古老的数学概念。它指的是一个正整数其所有真因子即除了自身以外的正因子之和恰好等于它本身。最小的完全数是6因为6的真因子是1、2、3而1236。下一个是28再下一个是496。这些数字在数学史上有着独特的地位从古希腊时代就被毕达哥拉斯学派所研究。我们今天要做的就是编写一个程序在给定的范围内高效、准确地找出这些数字的个数。为什么说它不止于“基础”因为随着范围的扩大最直接的暴力解法会立刻变得力不从心。如果你要在一秒内找出十万甚至百万以内的完全数简单的双重循环就会超时。这时你就不得不去思考因子的计算能否优化完全数本身是否有规律可循这道题就像一把钥匙它打开的第一扇门是编程语法但深入走下去你会接触到时间复杂度分析、数论知识欧几里得-欧拉定理甚至是对算法“优雅”与“效率”的权衡思考。它完美地诠释了编程学习中“题越简单坑越深”的普遍现象。接下来我将从一个多年编程教学和算法竞赛指导的角度彻底拆解这道题。我们不仅会实现一个能正确运行的“答案”更会深入探讨多种解法的优劣、它们背后的数学原理以及在实际编码中那些教科书上不会写的“坑”和技巧。无论你是正在学习编程的新手还是想重温基础、探究优化之道的老手这篇文章都将带你重新认识这个经典的“完全数问题”。2. 核心思路拆解与算法选型面对“求完全数个数”这个问题我们的第一反应通常是模拟定义对于一个数n从1到n-1遍历找出所有能整除n的数即因子把它们加起来看看和是否等于n。这个思路完全正确也是我们思维的起点。我们可以将其拆解为两个核心子问题第一如何高效地求出一个数的所有真因子之和第二如何在指定范围内对每个数应用第一步并计数。2.1 算法一朴素暴力法这是最直观的解法我们称之为“朴素暴力法”。其伪代码如下初始化计数器count 0。对于范围[1, N]内的每一个整数i a. 初始化sum 0。 b. 对于1到i-1之间的每一个整数j - 如果i % j 0则sum j。 c. 如果sum i则count 1。输出count。这个算法的时间复杂度是O(N²)因为外层循环N次内层循环平均N/2次。当N较小时比如N 10000现代计算机可以在瞬间完成。但一旦N超过10^5运行时间就会显著增长达到秒级甚至分钟级在算法竞赛的时限通常1-2秒内几乎必然超时。注意在实现时内层循环的上界可以优化为i-1但复杂度级别仍是O(N²)。这是我们需要优化的首要目标。2.2 算法二优化因子求和法仔细思考求因子和的过程。对于数i如果j是i的因子那么i / j也一定是i的因子除非j * j i。例如对于28因子有1, 2, 4, 7, 14。当我们找到因子2时我们同时知道了14 (28/2)也是因子。因此我们不需要遍历到i-1只需要遍历到sqrt(i)i的平方根即可。优化后的求因子和函数get_sum_of_proper_divisors(n)步骤如下如果n 1返回0因为1没有真因子。初始化sum 1因为1是所有大于1的数的因子。令limit int(sqrt(n))。从2遍历到limit a. 如果n % i 0 -sum i。 - 计算pair n // i。 - 如果pair ! i避免重复累加平方根如4*416中的4则sum pair。返回sum。这个优化将求单个数的因子和的时间复杂度从O(n)降到了O(sqrt(n))。那么整个问题的时间复杂度就变成了O(N * sqrt(N))。当N10^5时N * sqrt(N) ≈ 10^5 * 316 ≈ 3*10^7这个计算量在普通计算机上通常可以在1秒内完成性能有了质的飞跃。2.3 算法三利用完全数的数学性质欧几里得-欧拉定理这是本题的“终极优化”思路也是将一道编程题与数论知识结合的点睛之笔。欧几里得-欧拉定理指出一个偶数是完全数当且仅当它可以写成2^(p-1) * (2^p - 1)的形式其中p和(2^p - 1)都是素数。这里的(2^p - 1)被称为梅森素数。因此所有偶完全数都对应一个梅森素数。目前人类发现的完全数都是偶数且尚未发现任何奇完全数也未证明其不存在。基于这个定理我们的算法可以彻底改变我们不再需要检查区间内的每一个数。我们只需要生成形如2^(p-1) * (2^p - 1)的数并检查(2^p - 1)是否为素数梅森素数。生成的数如果落在指定范围内则计数加一。这个算法的时间复杂度主要取决于我们检查梅森素数的效率以及我们需要尝试的p的范围。由于完全数随着p增大而急剧增大指数增长对于通常的题目范围如N 10^8我们只需要尝试前几个pp2,3,5,7,13...即可。其时间复杂度可以认为是O(k * log(M))其中k是尝试的p的个数M是(2^p - 1)的大小log(M)是素数检测的复杂度。这比前两种方法快了几个数量级。方案选型考量教学与理解首选算法二。它平衡了难度和优化思想是学习算法优化的经典案例。竞赛与高性能在范围很大如N 10^7时必须使用算法三。但需要注意题目是否明确范围以及是否需要处理可能的奇完全数通常题目会说明只考虑偶完全数或者范围小到奇完全数不可能出现。代码简洁性算法三的代码可能更短但需要预先知道梅森素数的列表或者实现一个高效的素数检测函数如 Miller-Rabin 算法。在接下来的核心实现中我们将重点讲解算法二的优化实现并在最后探讨算法三的应用。因为算法二最能体现从朴素思维到优化思维的跨越是每个程序员都应该掌握的技能。3. 核心实现与代码详解我们将采用 Python 语言进行实现因为它语法简洁非常适合表达算法逻辑。我们将实现优化因子求和法算法二并给出完整的、带有详细注释的代码。3.1 关键函数优化求因子和这是整个程序的核心。我们将其封装为一个独立的函数提高代码的可读性和可复用性。def sum_of_proper_divisors(n): 计算一个正整数 n 的所有真因子除了自身以外的正因子之和。 采用遍历到 sqrt(n) 的优化方法。 参数: n: 正整数 返回: 真因子之和 (整数) if n 1: return 0 # 1 没有真因子 # 初始化总和为1因为1是所有大于1的数的因子 total 1 # 计算遍历的上限即 n 的平方根 limit int(n ** 0.5) # 从2开始遍历到平方根 for i in range(2, limit 1): if n % i 0: # i 是 n 的因子 total i # 计算对应的另一个因子 pair n // i # 避免重复累加平方根例如 n16, i4, pair4 if pair ! i: total pair return total代码要点解析边界处理if n 1: return 0。这是非常重要的边界条件。数字1的真因子定义是空集和为0。没有这行当n1时会错误地将1计入总和。初始化总和total 1。因为对于任何n 11都是其真因子。我们从2开始循环所以先把它加上。循环上界limit int(n ** 0.5)。使用** 0.5计算平方根比math.sqrt稍快且结果一致。int()向下取整确保limit是整数。因子成对出现当n % i 0时我们同时找到了i和pair n // i两个因子。这是一个关键优化将循环次数从n减少到sqrt(n)。避免重复if pair ! i:。当n是完全平方数时如i4, n16i和pair相等。如果不加判断因子4会被累加两次。3.2 主程序逻辑遍历与计数有了核心函数主程序就非常清晰了。我们接收一个上界N然后遍历从1到N的每个数判断是否为完全数。def count_perfect_numbers(N): 计算在 [1, N] 范围内完全数的个数。 参数: N: 范围上界 (正整数) 返回: 完全数的个数 (整数) count 0 for num in range(1, N 1): if sum_of_proper_divisors(num) num: count 1 # 调试时可以打印找到的完全数 # print(f找到完全数: {num}) return count # 主程序入口 if __name__ __main__: # 示例计算 10000 以内的完全数个数 N 10000 result count_perfect_numbers(N) print(f在 1 到 {N} 的范围内共有 {result} 个完全数。)运行与测试 将上述两段代码组合在一起运行程序。当N10000时程序会几乎瞬间输出结果。在我的测试中找到了三个完全数6, 28, 496。因此输出应为在 1 到 10000 的范围内共有 3 个完全数。你可以尝试修改N的值例如设为100000程序依然能快速运行并找到第四个完全数 8128。3.3 算法三的实现数论方法作为知识拓展我们来看一下基于欧几里得-欧拉定理的实现。这种方法不适用于通用范围的题目除非题目暗示或明确范围极大但作为编程与数学结合的典范值得了解。def is_prime_miller_rabin(n, k5): 使用Miller-Rabin素数检测算法判断一个数是否为素数。 这是一个概率算法但对于题目范围内的数k5已足够可靠。 if n 2: return False for p in [2, 3, 5, 7, 11]: if n % p 0: return n p # 将 n-1 写成 d * 2^s 的形式 s, d 0, n - 1 while d % 2 0: s 1 d // 2 # 进行k轮测试 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 def count_perfect_numbers_euclid_euler(N): 使用欧几里得-欧拉定理计算完全数个数。 仅适用于寻找偶完全数。 import random count 0 # 已知的梅森素数指数 p (2^p -1 是素数) # 对于 N 10^12检查前几个就足够了。 mersenne_exponents [2, 3, 5, 7, 13, 17, 19, 31] for p in mersenne_exponents: mersenne (1 p) - 1 # 等价于 2**p - 1但位运算更快 if not is_prime_miller_rabin(mersenne): continue perfect_num (1 (p - 1)) * mersenne # 等价于 2^(p-1) * (2^p -1) if perfect_num N: count 1 else: # 由于完全数增长极快一旦超过N后面的肯定也超过 break return count这个实现更复杂但效率极高。对于N10^12它几乎是在瞬间完成。需要注意的是is_prime_miller_rabin是一个概率算法但对于题目范围内的数设置适当的测试轮数如k5可以确保正确性。在严格的竞赛中如果题目范围已知且不大我们甚至可以硬编码已知的梅森素数指数。4. 性能分析与优化深潜我们已经实现了两种算法现在我们来深入分析它们的性能并探讨更多可能的优化方向。理解这些分析能帮助你在面对类似问题时做出更好的选择。4.1 时间复杂度实测对比我们用一个简单的实验来感受不同算法在时间上的差异。我们计算N100000以内的完全数个数并测量时间。import time def test_performance(N): print(f测试范围: N {N}) # 测试朴素暴力法 (仅作对比N大会很慢) # start time.time() # count_naive count_perfect_numbers_naive(N) # 需要实现朴素版本 # end time.time() # print(f朴素暴力法: {count_naive} 个, 耗时: {end-start:.4f} 秒) # 测试优化因子求和法 start time.time() count_opt count_perfect_numbers(N) end time.time() print(f优化因子求和法: {count_opt} 个, 耗时: {end-start:.4f} 秒) # 测试数论方法 start time.time() count_theory count_perfect_numbers_euclid_euler(N) end time.time() print(f数论方法: {count_theory} 个, 耗时: {end-start:.4f} 秒) if __name__ __main__: test_performance(100000) test_performance(1000000) # 可以尝试更大的数在我的电脑上普通配置运行N100000的结果大致如下优化因子求和法约 0.1-0.2 秒数论方法约 0.001 秒包含素数检测开销当N1000000时优化因子求和法可能需要1-2秒而数论方法依然在毫秒级。朴素暴力法在N50000时可能就需要数十秒因此不列入对比。4.2 算法二的进一步优化预计算与缓存虽然O(N * sqrt(N))的算法已经很快但我们还能更进一步。注意到在遍历num从1到N的过程中我们反复计算了许多数的因子和。例如计算28的因子和时我们计算了1,2,4,7,14。而计算56的因子和时我们又计算了1,2,4,7,8,14,28其中包含了重复计算。我们可以采用一种类似“筛法”的思想预先计算出从1到N每个数的因子和。其核心思路是对于每个数i我们知道它是哪些数的因子。那么我们可以把i加到这些数的因子和上去。def count_perfect_numbers_sieve(N): 使用筛法预先计算每个数的真因子和。 时间复杂度约为 O(N log log N)比 O(N*sqrt(N)) 更快。 # 初始化一个数组div_sum[i] 表示 i 的所有因子之和包括自身 # 我们先计算包括自身的和最后再减去自身得到真因子和。 div_sum [0] * (N 1) # 筛法过程 for i in range(1, N // 2 1): # 一个数 i 最多是 2*i 的因子 for multiple in range(i * 2, N 1, i): # 从 2*i 开始步长为 i div_sum[multiple] i # 计数完全数 count 0 for num in range(2, N 1): # 1 不是完全数 if div_sum[num] num: count 1 return count原理分析 外层循环i从1到N/2代表因子。内层循环multiple从2*i开始以i为步长递增直到超过N。这表示对于因子i我们把i加到所有是i的倍数的数multiple的因子和div_sum[multiple]上。这个过程类似于埃拉托斯特尼筛法求素数。复杂度这个算法的复杂度是O(N/1 N/2 N/3 ... N/N) ≈ O(N log N)。实际上这个求和是调和级数其渐进复杂度为O(N log N)。这比O(N * sqrt(N))要优。当N10^6时N log N约为2*10^7而N*sqrt(N)约为10^9有几十倍的差距。实操心得筛法在N很大如 10^6且内存充足时是比单个数求因子和更优的选择。但它需要O(N)的额外空间来存储div_sum数组。这是一种典型的“空间换时间”策略。4.3 不同场景下的算法选择指南根据题目要求和环境限制我们可以这样选择场景特征推荐算法理由教学演示、范围极小 (N 10^4)朴素暴力法逻辑最清晰易于理解问题本质。通用竞赛题、范围中等 (10^4 ≤ N 10^6)优化因子求和法实现简单效率足够是竞赛中的“万金油”解法。范围很大 (N ≥ 10^6)、内存充足筛法时间复杂度更优预处理后查询是O(1)。范围极大 (N ≥ 10^8)、或题目暗示数论方法唯一可行的方案利用数学性质降维打击。需要多次查询不同范围筛法预处理一次性O(N log N)预处理后每次查询只需O(1)。对于“1150: 【基础】求完全数的个数”这道题由于是基础题考察点通常就是优化因子求和法。但在实际解题时如果你能指出筛法或数论方法无疑是加分项体现了你的知识广度。5. 常见“坑点”与调试技巧即使思路正确在实现过程中也可能遇到各种问题。下面是我在多年编程和教学中总结的常见“坑点”及其解决方法。5.1 边界条件处理不当这是最常见的错误来源。数字1的处理错误认为1是完全数因为其因子只有自身但真因子和定义为00!1。正确在sum_of_proper_divisors函数中应对n 1的情况直接返回0。在主循环中可以从2开始遍历。循环边界与平方根错误for i in range(2, int(n**0.5)):。注意range的结束值是不包含的如果n**0.5恰好是整数如n9sqrt(9)3range(2, 3)只会迭代i2漏掉了因子3。正确limit int(n**0.5)然后for i in range(2, limit 1):。务必1。重复累加平方根因子错误当n为完全平方数时如n16, i4i和pair相等如果不加判断if pair ! i:因子4会被加两次。正确必须加上判断条件。5.2 性能陷阱与优化误区在循环内调用低效函数错误在求因子和的循环中使用math.sqrt(n)每次循环都计算一次平方根尽管在循环外计算更好或者使用n ** 0.5但未存储结果。正确在循环开始前计算一次limit int(n ** 0.5)并存储。不必要的类型转换和函数调用对于Python**0.5和math.sqrt()性能接近选择你习惯的即可。int()转换是必要的。忽略早期终止条件在求因子和的过程中如果sum已经大于n可以立即终止循环因为后续的因子只会让和更大。这只是一个微优化对于完全数这种稀有的数可能节省不了多少时间但体现了良好的编程习惯。def sum_of_proper_divisors_early_terminate(n): if n 1: return 0 total 1 limit int(n ** 0.5) for i in range(2, limit 1): if n % i 0: total i pair n // i if pair ! i: total pair # 早期终止如果当前和已经大于n肯定不是完全数 if total n: return total # 或者可以返回一个大于n的值表示失败 return total5.3 调试与验证技巧从小规模开始测试不要一开始就用N10000测试。先用N30测试你知道完全数只有6和28。手动验证程序输出是否正确。打印中间结果在怀疑因子和计算错误时可以临时修改函数打印出某个数的所有因子。def debug_divisors(n): divisors [1] limit int(n**0.5) for i in range(2, limit1): if n % i 0: divisors.append(i) pair n // i if pair ! i: divisors.append(pair) divisors.sort() print(f数字 {n} 的真因子: {divisors}, 和: {sum(divisors)}) return sum(divisors)使用已知结果验证前几个完全数是6, 28, 496, 8128, 33550336。用你的程序计算N10000应该得到3个6,28,496计算N100000应该得到4个多一个8128。这是快速验证程序正确性的好方法。性能 profiling如果程序很慢可以使用 Python 的cProfile模块找出耗时最长的函数。import cProfile cProfile.run(count_perfect_numbers(100000))这会告诉你时间主要花在了哪里是因子求和函数还是主循环。5.4 关于“完全数”本身的特殊考量奇完全数题目通常默认在给定的、较小的范围内如N 10^8只存在偶完全数。因为已知的完全数都是偶数且下一个偶完全数对应p13是33550336已经很大。如果你的范围极小更不用担心。如果题目没有特别说明通常按此处理。如果题目明确要求考虑“所有完全数”并给出了极大的范围如N10^18那你可能需要查阅资料了解奇完全数是否存在的研究现状目前未发现也未证明不存在但这已远超基础题范畴。范围与溢出在 Python 中大整数不会溢出所以无需担心。但在 C 或 Java 中计算2^(p-1) * (2^p - 1)时(2^p - 1)可能超出int甚至long long的范围。需要使用高精度计算或提前判断。这道“基础”题就像一颗多面的钻石从不同的角度观察能看到编程、数学和算法优化的不同光彩。它教会我们的远不止如何写一个循环。它训练了我们将数学定义转化为计算逻辑的基本功引导我们思考如何通过分析问题性质因子成对出现来优化算法并最终向我们展示了利用深层数学定理可以如何颠覆性地解决问题的威力。在编程学习的道路上多花时间咀嚼这样的“基础”题比盲目刷很多难题更有价值。下次再看到类似“求xxx数”的题目不妨先想想它的定义有没有可优化的特性有没有已知的数学定理这往往是通往高效解法的捷径。