質數與合數

**質數**只有 1 和自己兩個因數：2、3、5、7、11、13、17、19… **合數**有三個以上的因數。 **1 既不是質數也不是合數**——它只有一個因數。這個規定不是隨便訂的，是為了讓「質因數分解唯一」這件事成立（否則可以無限乘 1）。

**2 是唯一的偶質數**，因為其他偶數都有因數 2。

判斷一個數是不是質數，有一個大幅省力的技巧：**只需要試除到 √n**。 因為如果 n = a × b 且兩者都大於 √n，那麼 a × b 就會大於 n，矛盾。所以只要有因數，必定有一個不超過 √n。

判斷 97 是不是質數：√97 ≈ 9.8，所以只要試 2、3、5、7 這四個質數。都除不盡 → 97 是質數。不必試到 96。

找一定範圍內所有質數，用**埃拉托斯特尼篩法**：列出 2 到 n，先劃掉 2 的倍數（2 本身保留）、再劃掉 3 的倍數……剩下的就是質數。

質數在現代密碼學裡是核心——RSA 加密的安全性就建立在「兩個大質數相乘容易、分解回去極難」這件事上。