這個計算機能做什麼
這是一款三合一的質數工具,一次滿足三種需求:(1)查詢第 n 個質數,也就是 \(\text{Prime}[n] = p_n\);(2)判斷指定的整數是否為質數,並回報它在質數序列中的位置;(3)依需求一次列出前 N 個質數。最前面的幾個質數依序為 2、3、5、7、11、13、17……。所謂質數,是指大於 1 的整數,而且它的正因數只有 1 和它本身。
使用方法
先選擇模式。在第 n 個質數模式中,輸入從 1 開始計算的位置 n(例如 100),計算機就會回傳 \(\text{Prime}[100] = 541\)。在質數判斷模式中,輸入任一整數(例如 97),它會告訴你這個數字是否為質數;若是,還會顯示它在質數序列中的編號 n。在列出前 N 個質數模式中,輸入你想要的質數個數,它就會以逗號分隔列出完整清單,並附上其中最大的質數 \(\text{Prime}[N]\)。
公式原理
質數判斷採用「試除法」:當一個數 p 在 2 到 p 的平方根之間找不到任何整數因數時,p 就是質數。
$$\text{N is prime} \iff \text{N} \ge 2 \;\wedge\; \nexists\, d \in \left[2,\;\sqrt{\text{N}}\,\right]: d \mid \text{N}$$實際運算時,先處理 2 這個偶數,之後只需在 \(d \times d \le p\) 的範圍內測試奇數因數 d,這樣速度快,又能避免浮點數誤差。要找第 n 個質數,則從 2、3、4…… 依序掃描候選數字,每遇到一個質數就計數一次,直到計數達到 n 為止。質數 m 的索引值等於 \(\pi(m)\),也就是小於或等於 m 的質數個數。
實際範例
以 97 為例。97 是奇數,因此我們依序測試 \(d = 3、5、7、9\)(因為 \(9^2 = 81 \le 97\),但 \(11^2 = 121 > 97\))。這些數字都無法整除 97,所以 97 是質數。再計算 97(含)以內的質數共有 2、3、5……97,總共 25 個,因此 97 是第 25 個質數:\(\text{primeIndex} = 25\)。
質數參考:前 25 個質數與索引檢查點
索引 \(n\) 是質數在遞增質數序列中的位置,因此 \(p_n\) 表示第 \(n\) 個質數。下表列出前 25 個質數。
| n | pn | n | pn | n | pn | n | pn | n | pn |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 6 | 13 | 11 | 31 | 16 | 53 | 21 | 73 |
| 2 | 3 | 7 | 17 | 12 | 37 | 17 | 59 | 22 | 79 |
| 3 | 5 | 8 | 19 | 13 | 41 | 18 | 61 | 23 | 83 |
| 4 | 7 | 9 | 23 | 14 | 43 | 19 | 67 | 24 | 89 |
| 5 | 11 | 10 | 29 | 15 | 47 | 20 | 71 | 25 | 97 |
索引檢查點
| 陳述 | 數值 | 意義 |
|---|---|---|
| \(p_{100}\) | 541 | 第 100 個質數是 541 |
| \(p_{168}\) | 997 | 第 168 個質數是 997,也是小於 1000 的最大質數 |
| \(p_{1000}\) | 7919 | 第 1000 個質數是 7919 |
| \(\pi(10)\) | 4 | 不大於 10 的質數:2、3、5、7 |
| \(\pi(100)\) | 25 | 不大於 100 的質數有 25 個(最後一個是 97) |
| \(\pi(1000)\) | 168 | 不大於 1000 的質數有 168 個 |
| \(\pi(10000)\) | 1229 | 不大於 10,000 的質數有 1229 個 |
請注意兩種記號之間的關係:若 \(p\) 是質數,則只有當 \(p = p_n\) 時,才有 \(\pi(p) = n\)。例如,\(\pi(997) = 168\),且 \(p_{168} = 997\)。
質數相關名詞解釋
- 質數:大於 1 的正整數,且其正因數只有 1 和它自己(例如 2、3、5、7、11)。
- 合數:大於 1 的正整數,且至少有一個除了 1 和它自己以外的因數(例如 4、6、9、15)。
- 1 很特別:數字 1 既不是質數也不是合數。它只有一個正因數,就是它自己。
- 2 是唯一的偶質數:其他所有偶數都能被 2 整除,因此都是合數。
- 質數索引(位置)n:質數在由小到大排列的質數列表中的順序。2 的索引是 1,3 的索引是 2,5 的索引是 3,依此類推,因此 \(p_n\) 表示第 \(n\) 個質數。
- 質數計數函數 \(\pi(x)\):小於或等於 \(x\) 的質數個數。例如 \(\pi(10) = 4\),\(\pi(100) = 25\)。
- 試除法:一種質性檢驗方法,將 \(p\) 依序除以從 2 到 \(\sqrt{p}\) 的每個整數 \(d\)。若都無法整除 \(p\),則 \(p\) 是質數。只需檢查到 \(\sqrt{p}\) 即可,因為任一因數對中,至少有一個數不大於 \(\sqrt{p}\)。
- 互質:若兩個整數的最大公因數為 1,則它們互質(相對質數)。兩個不同的質數一定互質,但互質的數不一定是質數(8 和 15 互質)。
- 孿生質數:相差 2 的一對質數,例如 (3, 5)、(11, 13)、(17, 19)、(29, 31) 和 (41, 43)。
常見問題
1 是質數嗎?不是。依定義,質數必須大於 1,所以 1 既不是質數,也不是合數。
唯一的偶質數是什麼?2 是唯一的偶質數;其他所有偶數都能被 2 整除。
第 100 個質數是多少?\(\text{Prime}[100] = 541\)。其他幾個參考點:\(\text{Prime}[10] = 29\)、\(\text{Prime}[25] = 97\)、\(\text{Prime}[50] = 229\)、\(\text{Prime}[223] = 1409\)。