質數計算機(第 n 個質數查詢與質數判定)

質數計算機(第 n 個質數查詢與質數判定)

熱門 AI Skill PRO

輸入計算

數學公式

Pn=第 n個質數,p 質數⇔p≥2∧∄d∈[2,p]:d|pP_{\text{n}} = \text{第 } \text{n}\text{個質數}, \quad p \text{ 質數} \iff p \ge 2 \;\wedge\; \nexists\, d \in [2,\sqrt{p}\,]: d \mid p
使用統計

廣告

結果

Prime[100] — 第幾個質數 100
541
質數索引 n 100
第 n 個質數,Prime[n] 541

回報本頁錯誤

這個計算機能做什麼

這是一款三合一的質數工具,一次滿足三種需求:(1)查詢第 n 個質數,也就是 \(\text{Prime}[n] = p_n\);(2)判斷指定的整數是否為質數,並回報它在質數序列中的位置;(3)依需求一次列出前 N 個質數。最前面的幾個質數依序為 2、3、5、7、11、13、17……。所謂質數,是指大於 1 的整數,而且它的正因數只有 1 和它本身。

突顯 20 以內質數的數線
數線上標出質數(2、3、5、7、11、13、17、19),合數不作標記。

使用方法

先選擇模式。在第 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 的質數個數。

廣告
將索引 n 對應到第 n 個質數的圖示
每個索引 n 對應其質數 \(p_n\):1→2、2→3、3→5、4→7。

實際範例

以 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\)。

最後更新:

數學和統計熱門計算器

查看全部數學和統計計算器