關於質數，台灣競賽方面似乎比較少提及，頂多學學篩法、根號檢驗法而已。
草提一下這兩個算法：
>>埃氏篩法：
//什麼毛啦顏色傳上來變得醜死了
O(N ln N)時間複雜度、O(N)記憶體，求出1~N所有的質數。
一些優化：
1. 僅 型如 6n ± 1 者有可能是質數（2 | 6n+2、3 | 6n+3、2 | 6n+4）
其實這個優化加下去已經可以達到一定速度了。
2. 用位元壓縮，記憶體僅需要(N/32)個int（排掉偶數可以剩下N/64，但個人認為沒必要）
一些應用：
1. 求出質因數個數：
2. 求Φ(n)：
即找出1~n-1中有幾個跟n互質的數。
因為有Φ(n) = n * Π(1 - (1/p)) 對每個質數p | n，所以可以用篩法作到。
// 另外，線性篩法我不會，所以省略...
相關題目：
TIOJ：1036、1260、1353、1514、1535
ACM：294
>>根號檢驗法：
O(√n)檢驗一個數是否為質數。
一些應用：
1. 質因數分解：
每次除到不能除，若<= √p都試完了剩下的那個一定是質數。
相關題目：
ACM：583
反正目前為止的台灣競賽幾乎都只注重以上兩者，相關題目也十分罕見（目前為止沒見過）
但是對於密碼學而言，以上算法都還不能讓人滿意。
>>Miller-Rabin：
一個能期望極快的判斷質數作法。
算法核心：
引理一：若p是質數，則a(p-1) mod p = 1 （費瑪小定理）
引理二：若x2 mod p = 1（其中x<p、p是質數）那x = p-1或x = 1 （證明就是用(x+1)(x-1) = kp）
然後若我們要測定n是否能通過以a為底的米勒拉賓測試
先把n-1 = 2r * d ， 其中d是奇數 也就是求出n-1最高含2的幾次方
那麼 如果 a (2r * d) mod n 不是1 就一定是合數 （引理一）
就繼續下去a (2(r-1) * d) mod n 得是n-1 或1（引理二）
如果是n-1即是通過檢測，如果是1就繼續遞迴直到 ad mod n
對int範圍的數字，只需要測 a = 2, 7, 61
對10^16內的數字，只需要測 a = 2, 3, 5, 7, 11, 13, 17, 61, 24251
所以只需要寫一個大數次方 + 主程序大概 20~30 行很OK。
虛擬碼就不附了，上次寫得爛爛的。
進一步可以參照Matrix67的相關文章。
>>Pollard-ρ：
還在學...
