53 lines
1.6 KiB
Python
53 lines
1.6 KiB
Python
"""
|
||
A palindromic number reads the same both ways.
|
||
The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
|
||
Find the largest palindrome made from the product of two 3-digit numbers.
|
||
"""
|
||
|
||
|
||
def is_palindrome(n: int) -> bool:
|
||
return str(n) == str(n)[::-1]
|
||
|
||
|
||
def initial_idea() -> None:
|
||
a = 999
|
||
b = 999
|
||
y = (0, 0)
|
||
max_palindrome = 0
|
||
for i in range(a, 99, -1):
|
||
for j in range(b, 99, -1):
|
||
product = i * j
|
||
if is_palindrome(product) and product > max_palindrome:
|
||
max_palindrome = product
|
||
y = (i, j)
|
||
print(f"{max_palindrome} = {y[0]} × {y[1]}")
|
||
|
||
|
||
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
|
||
|
||
|
||
if __name__ == "__main__":
|
||
initial_idea()
|
||
x, y = largest_palindrome_product()
|
||
print(f"{x} = {y[0]} × {y[1]}")
|