質數判斷計算機

質數判斷計算機

熱門 AI Skill PRO

輸入計算

請輸入一個大於 1 的整數。

數學公式

n=數字 是質數⇔n>1∧∄d∈[2,⌊n⌋]:nmodd=0n = \text{數字} \text{ 是質數} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0
使用統計

廣告

結果

結果: 2
質數
質數判斷結果
數字 2
因數 它的因數只有 1 和 2
前一個質數 沒有更小的質數
下一個質數 3

回報本頁錯誤

什麼是質數?

質數(也稱為「素數」)是指大於 1,且只有兩個正因數(1 與本身)的整數。如果一個數字的因數超過兩個,就稱為合數。數字 1 比較特別:它只有一個因數,因此既不是質數,也不是合數。這個計算機會判斷你輸入的數字是質數還是合數、列出它的所有因數,並顯示前一個與下一個質數。

質數排成單行點與合數排成矩形點陣的對比
質數無法用點排成矩形,而合數可以。

使用方法

在欄位中輸入一個大於 1 的整數後送出。工具會將它歸類為質數或合數、重新顯示該數字、列出所有因數(合數適用),並回報它下方最大的質數與上方最小的質數。

計算原理說明

我們採用具有 \(6k\pm1\) 最佳化的確定性試除法。首先把 2 與 3 視為已知質數,並排除偶數以及 3 的倍數。接著只測試形如 \(6k-1\) 與 \(6k+1\) 的候選因數(5、7、11、13……),測試範圍到 \(n\) 的平方根為止。如果都無法整除 \(n\),\(n\) 就是質數。判斷質數的條件可寫為:

$$n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0$$

之所以只需測試到平方根,是因為任何大於平方根的因數,必定會與一個小於平方根的因數成對出現。

廣告
圖示說明試除法只檢驗到 n 的平方根為止的除數
試除法只需測試從 2 到 n 的平方根之間的除數。

實例演算

以 \(n = 97\) 為例,它的平方根大約是 \(9.85\)。它是奇數,也不是 3 的倍數。我們測試 5(\(97 \bmod 5 = 2\))與 7(\(97 \bmod 7 = 6\))。下一個候選數是 11,但 \(11 \times 11 = 121 > 97\),所以停止測試。由於找不到任何因數,因此 97 是質數。前一個質數是 89,下一個質數是 101。

質數與合數:範例輸入比較

下表顯示試除法測試如何處理七個輸入值。平方根上界為 \(\lfloor\sqrt{n}\rfloor\),也就是必須嘗試的最大除數。如果從 2 到該上界之間的任何整數都無法整除 \(n\),那麼 \(n\) 就是質數。前一個質數與後一個質數,分別是嚴格小於與嚴格大於 \(n\) 的最近質數。

輸入值 n 狀態 所有因數 前一個質數 下一個質數 平方根上界 \(\lfloor\sqrt{n}\rfloor\)
2 質數 1, 2 無 3 1(沒有需要嘗試的除數;2 是唯一的偶數質數)
9 合數 1, 3, 9 7 11 3(3 可整除 9)
15 合數 1, 3, 5, 15 13 17 3(3 可整除 15)
49 合數 1, 7, 49 47 53 7(7 可整除 49)
91 合數 1, 7, 13, 91 89 97 9(7 可整除 91)
97 質數 1, 97 89 101 9(2、3、5、7、9 都無法整除 97)
121 合數 1, 11, 121 113 127 11(11 可整除 121)

看似質數的合數: 49、91 和 121 很容易被誤認為質數,因為它們是奇數,且不能被 3 或 5 整除。

  • \(49 = 7 \times 7\)
  • \(91 = 7 \times 13\)
  • \(121 = 11 \times 11\)

每個數都有一個不大於其平方根上界的除數,因此如果只檢查 2、3 和 5,就會錯誤地判定它們為質數。相比之下,97 在 9 以內沒有任何除數,所以它是質數。

廣告

關鍵術語與定義

質數
大於 1 的整數,且其僅有的正除數為 1 與它本身(例如 2、3、5、7、97)。
合數
大於 1 的整數,且至少有一個除了 1 與它本身以外的除數(例如 9、49、91)。數字 0 與 1 既不是質數也不是合數。
因數/除數
能整除 \(n\) 且無餘數的整數 \(d\)。對 15 而言,其因數為 1、3、5、15。
模運算(mod)
除法後的餘數。\(n \bmod d = 0\) 表示 \(d\) 恰好整除 \(n\)。例如,\(91 \bmod 7 = 0\),但 \(97 \bmod 7 = 6\)。
平方根上界
若 \(n = a \times b\) 且 \(a \le b\),則 \(a \le \sqrt{n}\)。因此任何合數都有一個介於 2 與 \(\lfloor\sqrt{n}\rfloor\) 之間的除數,超過此範圍的測試是不必要的。
試除法
一種質數判定法,以 2 至 \(\lfloor\sqrt{n}\rfloor\) 之間的候選除數去除 \(n\)。若任一除法的餘數為 0,則 \(n\) 為合數;否則為質數。此法簡單可靠,對中等大小的數字而言速度也很快。
6k±1 形式
每個大於 3 的質數都可寫成 \(6k-1\) 或 \(6k+1\)(k 為某個整數),因為 mod 6 的其他餘數都可被 2 或 3 整除。這使測試能跳過約三分之二的候選除數。反之則不成立:25、35、49 和 91 也具有此形式,但它們是合數。
孿生質數
相差 2 的兩個質數,例如 (3, 5)、(11, 13)、(17, 19) 和 (41, 43)。是否存在無限多對孿生質數,是數學中尚未解決的問題。

計算慣例與邊界情況

以下每個情況都在本計算機上實際執行過,結果欄就是它真正回傳的值。

情況輸入結果
1 是質數嗎?1既非質數也非合數
2 是質數嗎?2質數
0 是質數嗎?0無效

核對於 2026-11-08

常見問題

1 是質數嗎?不是。1 只有一個因數,所以它既不是質數,也不是合數。

2 是質數嗎?是的。2 是最小的質數,也是唯一的偶質數,它沒有前一個質數。

為什麼只有合數才列出因數?根據定義,質數的因數只有 1 與本身,因此工具只會直接說明這一點。合數可能有許多因數,會依照由小到大的順序列出。

最後更新:

數學和統計熱門計算器

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