什么是质数？
质数（也叫素数）是指大于 1、且只有 1 和它本身两个正因数的整数，例如 2、3、5、7、11、13。大于 1 但不是质数的数称为合数，它们可以写成若干个更小整数的乘积。使用这个计算器，你输入任意一个数，就能立刻知道它是不是质数；如果不是，它还会告诉你能整除它的最小因数。
素数无法组成矩形（1×n 除外），而合数可以。
如何使用这个计算器
在输入框中填入任意一个整数（0 或更大），然后提交。结果区会显示 是（该数为质数）或 否（该数为合数）。当结果为合数时，下方表格会列出大于 1 的最小因数，帮你迈出完整因数分解的第一步。
计算原理详解
要高效判断一个数是否为质数，只需测试到 \(n\) 的平方根为止的因数即可。因为如果 \(n\) 有一个比平方根大的因数，那它必然还有一个与之配对、比平方根小的因数，所以测到平方根就足够了。用数学语言表述：当 \(n > 1\)，且对于从 2 到 \(\lfloor\sqrt{n}\rfloor\) 的每一个整数 \(i\) 都有 \(n \bmod i \neq 0\) 时，\(n\) 就是质数。和逐一测试小于 \(n\) 的每个数相比，这种方法的计算量大大减少。
$$n \text{ is prime} \iff n > 1 \text{ and } n \bmod i \neq 0 \;\; \forall\, i \in [2, \sqrt{n}]$$
广告
只需检验到 n 的平方根为止的因数。
实例演示
以 \(n = 97\) 为例。它的平方根约为 \(9.85\)，因此我们测试 2、3、5、7、9 这几个因数。它们都不能整除 97（97 是奇数，也不能被 3、5、7 整除），所以 97 是质数。再看 \(n = 91\)，依次测试 2、3、5，再到 7 时发现 \(91 \div 7 = 13\) 正好整除，所以 91 是合数，最小因数为 7。
广告
如何手工判断一个数是否为质数
质数是大于 1 的整数，且其仅有的正因数是 1 和它本身。要检验整数 \(n\)，只需检查不超过 \(\lfloor\sqrt{n}\rfloor\) 的因数。如果 \(n\) 有一个大于其平方根的因数，那么它必定也有一个与之配对、小于平方根的因数。
排除 \(n < 2\)。0、1 以及负数都不是质数。
接受 2 和 3。两者都是质数。2 是唯一的偶质数。
排除偶数。任何大于 2 的偶数 \(n\) 都能被 2 整除，因此它是合数。
计算 \(\lfloor\sqrt{n}\rfloor\)。找出平方不超过 \(n\) 的最大整数。例如，\(14^2 = 196 \le 221 < 225 = 15^2\)，所以 \(\lfloor\sqrt{221}\rfloor = 14\)。
检验从 3 到 \(\lfloor\sqrt{n}\rfloor\) 的奇数因数，或只检验质数因数。对每个候选数 \(d\)，检查 \(n \bmod d = 0\) 是否成立。可利用下面的整除捷径加快速度。
作出判断。如果找到任何因数，\(n\) 就是合数，且第一个找到的因数就是它大于 1 的最小因数。如果没有任何数能整除 \(n\)，则 \(n\) 是质数。
整除捷径
能否被 3 整除：各位数字之和能被 3 整除。例如：51 的各位数字之和为 5 + 1 = 6，所以 51 = 3 × 17。
能否被 5 整除：末位数字是 0 或 5。
能否被 11 整除：从右边或左边开始，对各位数字取交替和。若结果为 0 或 11 的倍数，则该数能被 11 整除。例如：121 的结果为 1 − 2 + 1 = 0，所以 121 = 11 × 11。
示例 1：221 是质数吗？
221 ≥ 2，它是奇数，且不是 2 或 3。
\(\lfloor\sqrt{221}\rfloor = 14\)，因此检验质数 3、5、7、11 和 13。
3：各位数字之和为 2 + 2 + 1 = 5，不能被 3 整除。
5：末位数字是 1，不能。
7：\(7 \times 31 = 217\)，且 \(221 - 217 = 4\)，有余数，不能。
11：交替和为 1 − 2 + 2 = 1，不能。
13：\(13 \times 17 = 221\)，所以 13 能整除 221。
221 是合数，它的最小因数是 13。
示例 2：97 是质数吗？
97 是奇数，且大于 3。
\(9^2 = 81 \le 97 < 100 = 10^2\)，所以 \(\lfloor\sqrt{97}\rfloor = 9\)。检验 3、5 和 7。
3：各位数字之和为 9 + 7 = 16，不能被 3 整除。
5：末位数字是 7，不能。
7：\(7 \times 13 = 91\)，且 \(97 - 91 = 6\)，有余数，不能。
在 9 以内没有任何数能整除 97，因此 97 是质数。
这种手工方法适用于小数和中等大小的数。对于非常大的数，试除法会变得很慢，此时改用专门的素性检验方法。
常见问题
1 是质数吗？不是。按照定义，质数必须大于 1，因此 1 既不是质数，也不是合数。
2 是质数吗？是的。2 是唯一的偶质数，其他所有偶数都能被 2 整除。
为什么只测到平方根就够了？因数总是成对出现，两两相乘等于 \(n\)。如果一对因数都大于 \(\sqrt{n}\)，它们的乘积就会超过 \(n\)，这显然不可能——所以任意一对因数中，至少有一个不大于 \(\sqrt{n}\)。