68 lines
2.0 KiB
Python
68 lines
2.0 KiB
Python
import time
|
||
|
||
|
||
def timer(func):
|
||
def wrapper(*args, **kwargs):
|
||
start_time = time.time()
|
||
result = func(*args, **kwargs)
|
||
end_time = time.time()
|
||
print(f"{func.__name__} took {end_time - start_time:.6f} seconds")
|
||
return result
|
||
|
||
return wrapper
|
||
|
||
|
||
def sum_of_non_abundant_numbers(limit=28123):
|
||
"""
|
||
计算所有不能表示为两个盈数之和的正整数之和
|
||
|
||
参数:
|
||
limit: 上限值，默认为28123（欧拉计划官方推荐值）
|
||
根据数学证明，所有大于28123的数都可以表示为两个盈数之和
|
||
|
||
返回:
|
||
total: 所有满足条件的正整数之和
|
||
"""
|
||
|
||
# 1. 使用筛法预处理所有数的真因数之和（高效O(n log n)）
|
||
divisor_sum = [0] * (limit + 1)
|
||
for i in range(1, limit + 1):
|
||
for j in range(i * 2, limit + 1, i):
|
||
divisor_sum[j] += i
|
||
|
||
# 2. 找出所有盈数
|
||
abundant_numbers = [i for i in range(12, limit + 1) if divisor_sum[i] > i]
|
||
|
||
# 3. 标记可以表示为两个盈数之和的数
|
||
can_be_expressed = [False] * (limit + 1)
|
||
abundant_set = list(set(abundant_numbers)) # 用于快速查找
|
||
|
||
# 遍历盈数对
|
||
n_abundant = len(abundant_set)
|
||
for i in range(n_abundant):
|
||
a = abundant_set[i]
|
||
if a > limit:
|
||
break
|
||
# 从i开始，允许两个相同的盈数相加（如12+12=24）
|
||
for j in range(i, n_abundant):
|
||
s = a + abundant_set[j]
|
||
if s > limit:
|
||
break
|
||
can_be_expressed[s] = True
|
||
|
||
# 4. 计算所有不能表示为两个盈数之和的数的和
|
||
total = sum(i for i in range(1, limit + 1) if not can_be_expressed[i])
|
||
|
||
return total
|
||
|
||
|
||
@timer
|
||
def main():
|
||
# 执行计算
|
||
result = sum_of_non_abundant_numbers()
|
||
print(f"所有不能表示为两个盈数之和的正整数之和是：{result}")
|
||
|
||
|
||
if __name__ == "__main__":
|
||
main()
|