素數判定器 (含質因數分解和前後素數)

什麼是素數

素數是大於 1 的自然數, 除 1 和自身外沒有正因子。最初幾個素數: 2、3、5、7、11、13、17、19、23、29、31、37。它們是整數算術的「原子」 — 每個 ≥ 2 的整數可唯一表示為素數的乘積 (算術基本定理)。

按慣例 1 不是素數。0 和負數不是素數。2 是唯一的偶素數 — 其他每個偶數除了 1 和自身外還能被 2 整除, 所以是合數。

測試如何工作

我們用試除法: 檢查能否被 2 整除, 然後 3, 5, 7, 11, ... 直到 √n。如果都不能幹淨整除, n 是素數。我們用 6k±1 最佳化, 只檢查 6k+1 或 6k−1 形式的候選 (因為所有 > 3 的素數都是這種形式), 減少 2/3 的測試。

試除法對 ~10^15 以下的 n 快速 (亞秒)。之後, 需要高階測試如 Miller-Rabin (機率) 或 AKS (確定性)。我們限制在 10^18 以防止瀏覽器在極端輸入上凍結。

為什麼素數重要

密碼學: RSA 加密把兩個約 1000 位的素數相乘, 產生難以分解的數。安全性依賴大數分解的難度 — 這個問題已研究數千年。

數學教育: 質因數分解是基礎。最大公約數、最小公倍數、模運算、分數、數論的概念都建立在質因數結構上。

電腦科學: 雜湊表大小、隨機數生成器、許多演算法用素數的獨特整除性屬性。