Project Euler第23题是一道经典的数论与算法结合的题目，核心目标是找出所有无法表示为两个非过剩数之和的正整数，并计算它们的总和。非过剩数的定义是一个数的所有真因数（小于自身的正因数）之和不超过该数本身，与之相对的是过剩数，即真因数之和大于自身的数。很多人在初次实现这道题的解法时，往往会因为细节处理不当导致结果错误或者运行效率极低。
非过剩数的判定逻辑与常见陷阱
要正确解决这道题，第一步是准确实现判定一个数是否为非过剩数的函数。真因数求和是最基础的操作，这里最常见的错误是把数字自身也计入因数之和。比如计算12的真因数时，正确的因数是1、2、3、4、6，和为16，而如果把12本身也算进去，和就会变成28，直接导致判定结果错误。另一个容易出错的点是循环上限的设置，很多人会用从1到n-1的循环遍历所有可能的因数，这种写法虽然逻辑正确，但会带来不必要的性能开销，实际上只需要遍历到该数的平方根即可，因为因数是成对出现的。
我们来看一段存在问题的真因数求和代码：
def wrong_sum_proper_divisors(n):
total = 0
for i in range(1, n): # 错误1：遍历到n-1，性能差且容易误加自身
if n % i == 0:
total += i
return total这段代码的问题首先是循环范围过大，当n是很大的数时，循环次数会非常多。其次如果循环条件写成range(1, n+1)就会把n本身加进去，导致结果错误。正确的实现应该控制循环上限为int(n**0.5) + 1，同时处理成对出现的因数，还要注意当因数是平方根时避免重复相加。正确的真因数求和函数实现如下：
def sum_proper_divisors(n):
if n <= 1:
return 0
total = 1 # 1是所有大于1的数的真因数
sqrt_n = int(n ** 0.5)
for i in range(2, sqrt_n + 1):
if n % i == 0:
total += i
other_divisor = n // i
if other_divisor != i: # 避免平方根重复相加
total += other_divisor
return total这个实现首先处理了n小于等于1的情况，因为1没有真因数，和为0。然后从2开始遍历到平方根，每找到一个因数就同时加上它和对应的成对因数，只有当两个因数相等的时候才只加一次，这样就避免了重复计算的问题，同时循环次数从O(n)降到了O(√n)，性能提升非常明显。非过剩数集合的生成与边界处理
生成所有非过剩数的时候，首先要明确题目中给出的已知条件：经过数学证明，所有大于28123的整数都可以表示为两个过剩数之和，因此我们只需要处理1到28123之间的数即可，超过这个范围的都不需要纳入最终的计算。这个边界是非常重要的，很多人会忽略这个条件，去处理更大的数，导致计算量无谓增加，甚至程序运行超时。另外还要注意，非过剩数包含完全数（真因数和等于自身的数，比如6、28）和亏数（真因数和小于自身的数，比如1、2、3、4、5等），这两类都属于非过剩数，不能遗漏。
生成非过剩数集合的常见错误是边界判断错误，比如有人会把上限设置为28124或者更大的值，或者错误地把过剩数当成非过剩数加入集合。我们可以先遍历1到28123的所有数，用前面实现的真因数求和函数计算每个数的真因数和，然后和原数比较，如果真因数和小于等于原数，就把它加入非过剩数集合。这里要注意，1的真因数和是0，0小于1，所以1属于非过剩数，这个结果符合定义，不能排除1。
以下是生成非过剩数集合的代码示例：
def generate_non_abundant_numbers():
max_limit = 28123
non_abundant = []
for n in range(1, max_limit + 1):
s = sum_proper_divisors(n)
if s <= n: # 真因数和小于等于自身，属于非过剩数
non_abundant.append(n)
return non_abundant
non_abundant_nums = generate_non_abundant_numbers()
print(f"1到28123之间的非过剩数数量：{len(non_abundant_nums)}")运行这段代码可以得到1到28123之间一共有多少非过剩数，我们可以先验证这个结果是否合理，比如小范围的非过剩数是否正确，比如前几个非过剩数是1、2、3、4、5、6、7、8、9、10、11、12？不对，12的真因数和是16，16大于12，所以12是过剩数，不属于非过剩数，这里的判断逻辑就可以帮我们自动排除12，不需要手动筛选。最终求和的正确遍历逻辑与优化
得到非过剩数集合之后，下一步是找出所有不能表示为两个非过剩数之和的数。这里最常见的逻辑陷阱是遍历方式错误，比如有人会嵌套遍历两个非过剩数集合，把所有可能的和都标记出来，但是标记数组的大小设置错误，或者遍历的时候重复计算了相同的和。正确的做法是用一个布尔数组来标记所有可以表示为两个非过剩数之和的数，数组的大小是28124（因为要包含28123这个索引），初始化为False，然后嵌套遍历非过剩数集合，对于每一对非过剩数a和b，如果a + b <= 28123，就把对应索引的数组值设为True。
这里要注意嵌套遍历的优化，比如可以让b从a开始遍历，避免重复计算a+b和b+a的情况，因为加法是交换律的，a+b和b+a是同一个和，重复计算只会浪费时间。另外还要注意，非过剩数集合里的数可能有重复吗？不会，因为我们是从1到28123依次遍历加入的，每个数只会出现一次，所以不需要去重。还有人会在遍历的时候把a和b的和超过28123的情况也纳入，这是没有意义的，因为题目已经说明超过28123的数都可以表示为两个过剩数的和，我们不需要处理，所以超过的部分可以直接跳过，减少计算量。
最终的求和逻辑代码实现如下：
def calculate_final_sum(non_abundant_nums):
max_limit = 28123
can_be_sum = [False] * (max_limit + 1) # 索引对应数值，标记是否可以表示为两个非过剩数之和
length = len(non_abundant_nums)
for i in range(length):
a = non_abundant_nums[i]
for j in range(i, length): # j从i开始，避免重复计算a+b和b+a
s = a + non_abundant_nums[j]
if s > max_limit:
break # 因为非过剩数是递增的，后面的和只会更大，直接跳出内层循环
can_be_sum[s] = True
# 计算所有不能标记为True的数的和
total = 0
for n in range(1, max_limit + 1):
if not can_be_sum[n]:
total += n
return total
final_result = calculate_final_sum(non_abundant_nums)
print(f"所有不能表示为两个非过剩数之和的正整数总和为：{final_result}")这段代码里内层循环加了break条件，因为当j增大到一定程度时，a + non_abundant_nums[j]会超过28123，后面的j更大，和只会更大，所以直接跳出内层循环可以节省大量时间。最后遍历1到28123的所有数，把没有被标记为可以表示为两个非过剩数之和的数加起来，就是最终的正确结果。整个流程下来，既避免了因数求和的错误，也处理了边界问题，还优化了遍历逻辑，不会出现结果错误或者运行效率低下的问题。在验证结果的时候，我们可以先小范围测试，比如先修改max_limit为较小的数，比如50，手动计算一下正确的结果，再对比程序的输出，确认逻辑没有问题之后再运行完整的28123范围的计算。这种分步验证的方式可以快速定位到逻辑错误的位置，比如如果小范围的结果不对，就可以先检查真因数求和函数是否正确，再检查非过剩数生成是否正确，最后检查求和逻辑是否正确，一步步排查问题，避免一开始就跑完整程序然后不知道哪里出错。
Project_Euler非过剩数算法优化修改时间：2026-08-18 11:23:17