质数判断器

判断一个整数是否为质数（只能被 1 和它本身整除），若不是，则在计算限度内给出能找到的质因数。对小于 3,317,044,064,679,887,385,961,981 的数，使用确定性的米勒–拉宾检验，所以“是或否”的答案是精确的，而不是概率。还会给出你输入的数前后最近的质数。

使用方法

1. 输入一个整数，逗号和空格会被忽略。
2. 查看它是质数、合数，还是两者都不是（0 和 1）。
3. 若是合数，查看其质因数分解、最小质因数和因数个数。
4. 通过上一个和下一个质数找到最近的质数。

计算公式

n is prime ⇔ n > 1 and no prime p ≤ √n divides n

试除到 √n 是教科书上的方法。对较大的 n，计算器使用以 2 到 41 的 13 个质数为底的米勒–拉宾检验，已证明在 3.3 × 10²⁴ 以下不会给出错误结论。合数再用试除法和波拉德 rho 方法分解。因数个数由质因数分解得出：若 n = p₁^a × p₂^b × …，则共有 (a + 1)(b + 1)… 个因数。

示例

91：√91 ≈ 9.5，所以只需试 2、3、5、7。91 ÷ 7 = 13，因此 91 是合数：91 = 7 × 13，有 4 个因数。97：2、3、5、7 都不能整除它，所以 97 是质数，相邻的质数是 89 和 101。360 = 2³ × 3² × 5，有 (3 + 1)(2 + 1)(1 + 1) = 24 个因数。