素数判定器 (含质因数分解和前后素数)

什么是素数

素数是大于 1 的自然数, 除 1 和自身外没有正因子。最初几个素数: 2、3、5、7、11、13、17、19、23、29、31、37。它们是整数算术的「原子」 — 每个 ≥ 2 的整数可唯一表示为素数的乘积 (算术基本定理)。

按惯例 1 不是素数。0 和负数不是素数。2 是唯一的偶素数 — 其他每个偶数除了 1 和自身外还能被 2 整除, 所以是合数。

测试如何工作

我们用试除法: 检查能否被 2 整除, 然后 3, 5, 7, 11, ... 直到 √n。如果都不能干净整除, n 是素数。我们用 6k±1 优化, 只检查 6k+1 或 6k−1 形式的候选 (因为所有 > 3 的素数都是这种形式), 减少 2/3 的测试。

试除法对 ~10^15 以下的 n 快速 (亚秒)。之后, 需要高级测试如 Miller-Rabin (概率) 或 AKS (确定性)。我们限制在 10^18 以防止浏览器在极端输入上冻结。

为什么素数重要

密码学: RSA 加密把两个约 1000 位的素数相乘, 产生难以分解的数。安全性依赖大数分解的难度 — 这个问题已研究数千年。

数学教育: 质因数分解是基础。最大公约数、最小公倍数、模运算、分数、数论的概念都建立在质因数结构上。

计算机科学: 哈希表大小、随机数生成器、许多算法用素数的独特整除性属性。