Python如何編程找出1000以內的所有完全數

# Python如何編程找出1000以內的所有完全數

## 什么是完全數？

**完全數（Perfect Number）**，又稱完美數或完備數，是指一個正整數等于其所有**真因子**（即除了自身以外的正約數）之和。例如：

- 6 的真因子：1, 2, 3  
  1 + 2 + 3 = 6  
  因此 6 是完全數。

- 28 的真因子：1, 2, 4, 7, 14  
  1 + 2 + 4 + 7 + 14 = 28  
  因此 28 也是完全數。

完全數在數學中具有重要地位，目前發現的完全數均為偶數，且與**梅森素數**密切相關。本文將介紹如何用 Python 編程找出 1000 以內的所有完全數。

---

## 算法思路

要找出完全數，需解決兩個核心問題：

1. **找出一個數的所有真因子**  
   遍歷從 1 到 n/2 的所有整數，判斷是否能整除 n。

2. **判斷真因子之和是否等于原數**  
   若滿足條件，則該數為完全數。

優化思路：
- 只需遍歷到 `int(n ** 0.5) + 1`，通過成對記錄因子減少計算量。
- 完全數稀少，1000 以內僅需驗證有限個數。

---

## Python 實現代碼

### 方法一：暴力遍歷法

```python
def find_perfect_numbers(max_limit):
    perfect_numbers = []
    for num in range(2, max_limit + 1):
        divisors = [1]  # 1 是所有數的真因子
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                divisors.append(i)
                if i != num // i:  # 避免重復添加平方根
                    divisors.append(num // i)
        if sum(divisors) == num:
            perfect_numbers.append(num)
    return perfect_numbers

print(find_perfect_numbers(1000))

輸出結果：
[6, 28, 496]

方法二：優化因子求和

利用數學性質減少計算次數：

def find_perfect_numbers_optimized(max_limit):
    perfect_numbers = []
    for num in range(2, max_limit + 1):
        sum_divisors = 1  # 初始化時包含1
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                sum_divisors += i
                if i != num // i:
                    sum_divisors += num // i
        if sum_divisors == num:
            perfect_numbers.append(num)
    return perfect_numbers

print(find_perfect_numbers_optimized(1000))

代碼解析

1. 因子查找范圍

   • 只需檢查從 2 到 √n 的整數，因為若 i 是因子，則 n/i 也是因子。
   • 例如：對于 28，檢查到 5 即可發現因子對 (2,14) 和 (4,7)。

2. 去重處理

   • 當 i 是 n 的平方根時（如 16 的因子 4），避免重復添加。

3. 性能對比

   • 方法一存儲所有因子，占用更多內存。
   • 方法二直接累加，效率更高。

數學背景擴展

完全數的性質

1. 所有已知完全數均為偶數，形如 2^(p-1) * (2^p - 1)，其中 2^p - 1 是梅森素數。

   • 例如：6 = 2^1 * (2^2 - 1)
     28 = 2^2 * (2^3 - 1)

2. 未解之謎

   • 是否存在奇完全數仍是數學難題。

歐幾里得-歐拉定理

若 2^p - 1 是素數（梅森素數），則 2^(p-1) * (2^p - 1) 是完全數。利用此性質可進一步優化算法：

def euclid_euler_perfect(max_limit):
    perfects = []
    p = 2
    while True:
        mersenne = 2 ** p - 1
        if mersenne > max_limit:
            break
        if is_prime(p) and is_prime(mersenne):
            perfect = (2 ** (p - 1)) * mersenne
            if perfect <= max_limit:
                perfects.append(perfect)
        p += 1
    return perfects

# 需實現素數判斷函數 is_prime()

總結

1. 1000 以內的完全數：6, 28, 496。
2. 編程要點：
   
   • 因子成對查找提升效率。
     
   • 直接求和比存儲因子更節省資源。
3. 數學方法：結合梅森素數可快速生成完全數。

通過本文，讀者不僅能掌握 Python 實現，還能理解完全數背后的數學邏輯。嘗試將代碼擴展到更大的范圍（如 10000），觀察性能變化吧！ “`

注：實際字數約 900 字，可根據需要擴展數學證明或歷史背景部分。