寻找完全数的高效算法：是否存在快于O(N²)的实现？

有没有快于O(N²)的算法？ #

当然有，而且有不少复杂度远低于O(N²)的方案，最经典的是约数和筛法，时间复杂度可以达到O(N log N)，比O(N²)高效几个数量级：

• 核心思路：反过来操作，不是逐个计算每个数的约数，而是遍历每个可能的约数d，将d加到所有d的倍数（除了d自身）的约数和中。比如从d=2开始，对每个m=2d, 3d, ... ≤N，执行sum[m] += d。最后遍历sum数组，满足sum[i] == i的数就是完全数。
• 复杂度分析：每个d的倍数数量是N/d，总运算量是N*(1/2 + 1/3 + ... + 1/N)，这个和的近似值是N log N，远优于O(N²)。

如果N非常大，还可以利用欧几里得-欧拉定理来生成完全数：已知所有偶完全数都形如2^(p-1)*(2^p - 1)，其中2^p -1是梅森素数。你只需要找出所有满足2^(p-1)*(2^p -1) ≤N的梅森素数，就能直接得到范围内的所有偶完全数。这种方法的复杂度取决于梅森素数的查找效率，在N极大时，比筛法高效得多，因为梅森素数的数量极少。

通用提速方案 #

结合你提到的「排除奇数完全数」的假设，再搭配以下方案可以进一步减少计算量：

• 直接跳过奇数：只处理范围内的偶数，直接减少一半的计算量。比如在筛法中，只初始化偶数的sum数组；或者在单个检查数时，直接跳过所有奇数。
• 优化单个数字的约数和计算：如果不用筛法，单独检查某个数n时，不需要遍历到n-1，只需要遍历到√n。因为约数是成对出现的（d和n/d），找到d是n的约数后，若d≠n/d且n/d≠n，就把两者都加到和里。这样单个数字的检查复杂度从O(n)降到O(√n)，整体遍历的复杂度是O(N√N)，也远好于O(N²)。
• 提前终止计算：在计算单个n的约数和时，一旦当前的和已经超过n，就可以直接停止后续计算，避免不必要的运算。
• 利用梅森素数的性质：如果你的N较大，优先用欧几里得-欧拉定理生成完全数，不需要遍历所有数，只需要验证哪些梅森素数对应的完全数在范围内即可。

内容的提问来源于stack exchange，提问作者fvim