萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 判斷盈數: 真因子和大於自身的自然數

定義

盈數 又稱豐數、過剩數。若一正整數 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)

優化:只迭代至 √n


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...

相關概念

  • 完全數:真因子和等於自身 (6, 28, 496...)
  • 虧數:真因子和小於自身 (質數、1、大多數合數)
  • 所有大於 20161 的整數皆可寫為兩個盈數之和
copyright © 萬盛學電腦網 all rights reserved