完美数算法Python实战：从暴力解法到sqrt优化详解

最近看到一个技术社区的热门讨论：一位新人工程师在入职不久后，成为某个遗留系统的负责人，因一次偶然操作触发了深藏多年的代码缺陷，最终导致一次S0级别的高危事故。他正在困惑，自己是否需要为此承担全部责任。

评论区观点各异，有的认为“负责人即第一责任人”，有的则强调“这是历史技术债务，不应由新人全盘接手”。从技术管理角度看，此事可分层剖析：若操作完全遵循既定流程，未进行任何越权或违规改动，那么事故的根本诱因是系统长期累积的设计缺陷与测试缺口，新人仅是触发了最后一个条件。因此，技术层面的“锅”不应完全扣在个人头上。然而，作为系统负责人，事故后的复盘分析、文档补全、缺陷修复的推动等管理责任，无疑是需要承担的。

换言之，承担“全部技术责任”有失公允，但完全置身事外也不现实。这次经历无疑是一堂代价高昂的实战课，它既可能成为简历上的一个深刻注脚，更能转化为未来技术决策与风险把控的宝贵经验。

面试题解析：完美数算法与Python实现

本文旨在清晰讲解「完美数」这一经典算法问题，并提供从基础到优化的Python实现代码，力求简洁易懂。

完美数定义

首先明确概念。如果一个正整数恰好等于它所有“真因子”（即除了自身以外的正因子）之和，则称其为“完美数”。

例如：

• 数字6
  • 其因子为：1, 2, 3, 6
  • 真因子为：1, 2, 3
  • 1 + 2 + 3 = 6，等于自身，故6是完美数。
• 数字28
  • 真因子为：1, 2, 4, 7, 14
  • 1 + 2 + 4 + 7 + 14 = 28，同样满足条件。

常见的完美数有：6, 28, 496, 8128。更大的完美数在常规算法面试与编程中较少涉及。

方法一：朴素暴力解法

最直接的思路是遍历所有可能的真因子并求和。

算法逻辑：遍历从1到n-1的所有整数，如果能整除n，则累加该数。最后判断累加和是否等于n。

Python实现：

def is_perfect_naive(n: int) -> bool:
    """朴素判断法，时间复杂度 O(n)"""
    if n <= 1:
        return False  # 1及以下的数不是完美数

    total = 0
    for i in range(1, n):
        if n % i == 0:
            total += i
    return total == n

测试示例：

print(is_perfect_naive(6))   # 输出 True
print(is_perfect_naive(28))  # 输出 True
print(is_perfect_naive(10))  # 输出 False

该方法实现简单，但效率较低。当n较大时（例如10^8），O(n)的时间复杂度将导致无法接受的计算耗时。

方法二：基于平方根的优化解法

利用数学性质进行优化：若i是n的因子，则n // i也一定是n的因子，且成对出现。我们只需遍历到sqrt(n)即可找到所有因子对。

优化核心：

1. 遍历范围从2到int(sqrt(n))。
2. 当i能整除n时，将i和n // i同时加入总和（需排除i == n // i的重复情况）。
3. 注意1是所有数的因子，可预先加入总和。

Python实现：

import math

def is_perfect(n: int) -> bool:
    """优化判断法，时间复杂度 O(sqrt(n))"""
    if n <= 1:
        return False

    total = 1  # 1 总是因子
    limit = int(math.sqrt(n))
    for i in range(2, limit + 1):
        if n % i == 0:
            total += i
            other = n // i
            if other != i:  # 避免平方根因子重复累加
                total += other
    return total == n

性能对比：对于n=10^8，朴素方法需循环10^8次，而优化方法仅需约10^4次，效率提升近万倍。

扩展：查找指定范围内的所有完美数

常见面试题要求找出某一上限内的所有完美数。只需遍历区间并对每个数调用优化后的判断函数即可。

Python实现：

def find_perfect_numbers(limit: int):
    """返回 [1, limit] 区间内所有完美数"""
    result = []
    for num in range(2, limit + 1):
        if is_perfect(num):
            result.append(num)
    return result

if __name__ == "__main__":
    print("10000以内的完美数：", find_perfect_numbers(10000))
    # 输出：[6, 28, 496, 8128]

该算法整体时间复杂度约为O(N * sqrt(N))，在合理的数据范围内（如N <= 10^5）可以高效运行。掌握此算法思路对解决因子相关、质数判断等问题均有助益。