Python实现亲密数对查找算法与优化

1. 亲密数对：数学之美与编程实践

第一次听说"亲密数对"这个概念是在大学数论课上，当时就被这种奇妙的数字关系吸引了。简单来说，亲密数对指的是两个正整数，其中每一个数的真因数之和等于另一个数。比如220和284就是最经典的一对——220的真因数之和是1+2+4+5+10+11+20+22+44+55+110=284，而284的真因数之和是1+2+4+71+142=220。

这种数字间的"亲密"关系不仅有趣，在实际编程面试中也经常出现。本文将带你从零开始，用Python实现一个查找指定范围内所有亲密数对的程序。无论你是编程新手还是想巩固算法基础，这个练习都能帮助你提升对数学问题的编程解决能力。

2. 算法设计与核心思路

2.1 亲密数对的数学定义

要编写查找程序，首先需要严格定义亲密数对。对于两个不同的正整数A和B，如果满足：

• σ(A) - A = B
• σ(B) - B = A

其中σ(n)表示n的所有正因数之和，那么(A,B)就构成一对亲密数对。因为σ(n)-n就是n的真因数之和（即不包括n本身的因数之和）。

2.2 基础算法流程

最直接的算法思路可以分解为以下几步：

1. 对于范围1到n的每个数i，计算其真因数之和s
2. 对于这个s，再计算它的真因数之和s'
3. 如果s'等于i且i不等于s，则(i,s)就是一对亲密数对
4. 为避免重复输出，当i < s时才记录这对数

这个算法虽然直观，但效率不高，时间复杂度为O(n²)。我们需要进一步优化。

2.3 优化思路分析

通过观察可以发现：

1. 真因数之和的计算会被重复多次，可以缓存结果
2. 如果i的真因数之和s大于n，可以立即跳过
3. 亲密数对中较小的数通常小于较大的数，可以适当减少检查范围

基于这些观察，我们可以引入记忆化存储来优化性能。

3. Python实现详解

3.1 计算真因数之和

python复制def sum_proper_divisors(n):
    if n == 1:
        return 0
    sum_div = 1  # 1是所有大于1的数的真因数
    sqrt_n = int(n**0.5)
    for i in range(2, sqrt_n + 1):
        if n % i == 0:
            sum_div += i
            counterpart = n // i
            if counterpart != i:  # 避免重复添加平方数的情况
                sum_div += counterpart
    return sum_div

这个函数通过遍历到√n来高效计算真因数之和。对于每个能整除n的数i，我们把i和n/i都加到总和中（注意避免平方数的重复添加）。

3.2 查找亲密数对的主函数

python复制def find_amicable_pairs(n):
    if n < 2:
        return []
    
    # 预计算所有数的真因数之和
    sum_dict = {i: sum_proper_divisors(i) for i in range(1, n+1)}
    
    amicable_pairs = []
    for i in range(2, n+1):
        s = sum_dict[i]
        if s > n or s <= i:  # 避免重复和超出范围
            continue
        if sum_dict.get(s, 0) == i:  # 检查是否互为真因数之和
            amicable_pairs.append((i, s))
    
    return amicable_pairs

这个实现首先预计算了范围内所有数的真因数之和，存储在字典中以避免重复计算。然后遍历每个数，检查其真因数之和是否满足亲密数对的条件。

3.3 性能优化版本

对于更大的n值（比如n>100,000），我们可以进一步优化：

python复制def find_amicable_pairs_optimized(n):
    if n < 2:
        return []
    
    sum_div = [0] * (n + 1)
    for i in range(1, n//2 + 1):
        for j in range(2*i, n+1, i):
            sum_div[j] += i
    
    amicable_pairs = []
    for i in range(2, n+1):
        s = sum_div[i]
        if s > n or s <= i:
            continue
        if sum_div[s] == i:
            amicable_pairs.append((i, s))
    
    return amicable_pairs

这个版本使用筛法来计算真因数之和，时间复杂度降低到O(n log n)，适合处理更大的输入范围。

4. 算法测试与验证

4.1 测试用例设计

好的测试应该包含：

• 边界情况：n=1, n=2
• 已知的亲密数对：(220,284), (1184,1210)
• 较大范围的检查
• 不含亲密数对的范围

pytho复制