素數與篩法：邏輯的原子

演算法背後的故事：希臘人的過濾器

西元前 200 年，亞歷山大圖書館的館長 埃拉托斯特尼 (Eratosthenes) 對素數著了迷——那些沒有「朋友」（除了 1 和自己以外沒有因數）的數字。

他意識到，尋找素數就像在河裡淘金。妳不需要拿起每一塊石頭看她是不是金子，妳需要建一個 篩子 (Sieve)。

想像一張從 2 到 100 的數字網格。

1. 從 2 開始。她是素數。現在，伸手「劃掉」網格中所有 2 的倍數（4, 6, 8…）。她們絕對不是素數。
2. 移動到 3。她是素數。劃掉所有 3 的倍數（6, 9, 12…）。
3. 跳過 4（她已經被劃掉了）。
4. 移動到 5…

當妳完成時，剩下的只有純淨的「黃金」。這就是 埃拉托斯特尼篩法。直到今天，她依然是尋找小規模素數最有效的方法之一。

為什麼需要它？

• 密碼學： RSA 加密基於分解兩個巨大素數乘積的難度。尋找這些素數是構建安全互聯網的第一步。
• 哈希： 哈希表的大小通常取素數，因為這能最大限度地減少模運算中的「碰撞」。
• 遊戲機制： 在遊戲中使用素數作為刷新率或週期性事件，以防止她們過於頻繁地同步（重疊）。

演算法是如何「思考」的

篩法是一個消除引擎。

1. 素數假設： 我們開始時假設每個數字都是素數（一個全是 True 的布爾陣列）。
2. 劃線： 從 2 開始，如果一個數字仍為 True，我們就遍歷她的倍數並設為 False。
3. 優化 (平方規則)： 妳不需要從 $2 imes P$ 開始劃線，妳可以從 $P imes P$ 開始。因為比 $P^2$ 小的倍數一定已經被更小的素數處理過了。
4. 邊界： 要找到 $N$ 以內的所有素數，妳只需要處理到 $\sqrt{N}$ 即可。

工程決策：大素數問題

篩法在尋找 1000 萬以內的所有素數時表現出色。但如果妳需要一個 2048 位元的單一素數用於 TLS 證書呢？

• 篩法需要的記憶體將超過全宇宙的上限。
• 此時，工程師會使用 概率性素性測試（如 Miller-Rabin）。這些測試不一定能 100% 證明一個數是素數，但她們能在幾毫秒內以 99.9999999% 的確定性完成。在工程中，這種速度下的「足夠好」就是標準。

實作參考 (Python)

def sieve_of_eratosthenes(n):
    # 1. 創建篩子，假設所有數都是素數
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False # 0 和 1 不是素數
    
    # 2. 遍歷到 sqrt(n)
    p = 2
    while p * p <= n:
        if is_prime[p]:
            # 3. 從 p*p 開始劃掉所有 p 的倍數
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    
    # 4. 收集倖存者
    return [i for i, prime in enumerate(is_prime) if prime]

# 範例
print(f"50 以內的素數: {sieve_of_eratosthenes(50)}")

小結

素數教會我們：複雜性是由簡單構建的。透過濾除合數的雜音，我們抵達了數學的基礎構件。它提醒我們，在安全和工程領域，最堅固的基石往往也是最基礎的那些。