Python 求質數死循環修復：從暴力遞歸到高效篩法

原始問題代碼

for i in range(1, 10000):
    for n in range(1, (i - 1)):
        if (i % n) != 0:
            print i
# 問題：邏輯錯誤導致大量重複輸出，非死循環但極其低效且結果錯誤

錯誤分析

• 內層循環 range(1, i-1) 從 1 開始，i % 1 == 0 恆成立，導致 if 判斷邏輯反了（應檢測 能否整除）。
• 未及時 break，一旦發現因子應立即跳出內層循環。
• 範圍 10000 以內用試除法還可接受，但寫法決定性能天花板。

修正版：試除法優化

import math

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 只需檢測到 sqrt(n)，步長 2 跳過偶數
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

def print_primes(limit):
    for i in range(2, limit + 1):
        if is_prime(i):
            print(i)

print_primes(1000)

進階：埃拉托斯特尼篩法（Sieve of Eratosthenes）

求 10000 以內質數，篩法 O(n log log n) 遠快於試除法 O(n√n)。

def sieve(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            # 從 i*i 開始標記，步長 i
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return [i for i, prime in enumerate(is_prime) if prime]

primes = sieve(10000)
print(primes[:20])  # 前 20 個質數
print("總數:", len(primes))

性能對比 (10000 以內)

核心知識點總結

1. 質數定義：大於 1 且除 1 和自身外無其他因數。
2. 試除優化：只除到 √n，跳過偶數。
3. 篩法思想：標記合數，剩下的即質數，適合批量求取。
4. Python 技巧：列表推導式、enumerate、切片輸出。

掌握篩法，百萬以內質數也能瞬間搞定。