盈數 又稱豐數、過剩數。若一正整數 n 的所有真因子 (不含自身的因子) 之和大於 n,則為盈數。
等價條件:σ(n) > 2n (含自身的所有因子和大於兩倍自身)。
def is_abundant(n):
if n < 1:
return False
sum_factors = 0
for i in range(1, n): # 真因子:1 到 n-1
if n % i == 0:
sum_factors += i
return sum_factors > n
# 測試
for n in [12, 18, 20, 24, 30]:
print(f'{n}: {"盈數" if is_abundant(n) else "非盈數"}')
# 12: 盈數 (1+2+3+4+6=16>12)
# 18: 盈數 (1+2+3+6+9=21>18)
import math
def is_abundant_fast(n):
if n < 1:
return False
total = 1 # 1 永遠是因子
sqrt_n = int(math.isqrt(n))
for i in range(2, sqrt_n + 1):
if n % i == 0:
total += i
other = n // i
if other != i:
total += other
return total > n
複雜度從 O(n) 降為 O(√n)。
12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100...