什么是质数?
质数(也叫素数)是大于 1 的整数,且只有 1 和它本身两个正约数。如果一个数除了 1 和本身之外还有其他约数,就是合数。数字 1 比较特殊:它只有一个约数,所以既不是质数也不是合数。本计算器会判断你输入的数是质数还是合数,列出它的因数,并显示前一个和后一个质数。
使用方法
在输入框中填入一个大于 1 的整数,然后提交。工具会判定它是质数还是合数,重述这个数,列出它的所有因数(合数才有),并给出比它小的最大质数和比它大的最小质数。
计算原理
我们采用确定性试除法,并结合 \(6k \pm 1\) 优化。首先把 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 = 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\) 为某个整数),因为模 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 和它本身,所以工具直接说明这一点即可。合数则可能有许多因数,会按从小到大的顺序列出。