Files
2025-12-26 17:35:14 +08:00
..
2025-12-26 17:35:14 +08:00
2025-12-26 17:35:14 +08:00

从数学角度,快速找到两个三位数相乘得到的最大回文数。

核心数学洞察

首先,两个三位数最大的乘积是: 999 × 999 = 998001 。所以最大的回文数一定是6位的。

1. 回文数的结构性质

一个6位回文数可以表示为


\overline{abccba} = 100000a + 10000b + 1000c + 100c + 10b + a = 100001a + 10010b + 1100c = 11 \times (9091a + 910b + 100c)

关键结论所有6位回文数都是11的倍数

2. 质因数推论

如果乘积 p \times q 是回文数且这个回文数是11的倍数那么

  • 由于11是质数p和q中至少有一个是11的倍数
  • 这样搜索空间直接缩小为原来的1/11

最优算法策略

def largest_palindrome_product():
    max_palindrome = 0
    max_factors = (0, 0)
    
    # 外层循环从大到小且只遍历11的倍数
    for i in range(990, 100, -11):  # 从990开始最大的11的倍数
        # 内层循环从i开始避免重复利用乘法交换律
        for j in range(999, i-1, -1):
            product = i * j
            
            # 提前终止:如果乘积已小于当前最大值
            if product <= max_palindrome:
                break
                
            # 检查是否为回文数
            if str(product) == str(product)[::-1]:
                max_palindrome = product
                max_factors = (i, j)
                break  # 找到即可跳出内层循环
                
    return max_palindrome, max_factors

# 结果906609 = 913 × 993