质数判断 + 质因数分解
—
质数判断
Miller-Rabin/区间内质数表/因式分解
423 次访问
100 以内质数
关于本工具
了解工具定位 · 使用场景 · 对比优势
使用场景
RSA密钥生成
信息安全从业者在生成 RSA 密钥对时，需要挑选两个大质数 p 和 q。本工具的 Miller-Rabin 算法可快速验证候选数的质数性，区间质数表功能则能直接列出指定范围内的所有质数，省去手动筛选的繁琐，确保密钥生成环节的数学基础可靠。
数论作业检查
数学系学生在完成数论作业（如证明质数分布规律、分解大整数）后，需要验证自己的计算结果。本工具的因式分解功能可快速拆解合数的质因数，质数判断功能则能确认候选数是否为质数，帮助学生在提交前快速自查，避免因计算失误丢分。
密码学教学演示
密码学教师在课堂上讲解质数在公钥加密中的作用时，需要一个即时演示工具。本工具支持输入任意位数的大数进行质数判断，并能展示因式分解过程，让学生直观理解大整数分解的难度，从而理解 RSA 等算法的安全性基础。
科研数据筛选
科研人员在处理大量整数序列（如基因序列编码、信号处理中的质数周期）时，需要快速筛选出其中的质数。本工具的区间质数表功能可一键输出指定范围内的所有质数，配合因式分解功能分析合数结构，大幅提升数据处理效率。
编程竞赛备题
算法竞赛选手在练习数论相关题目（如质数判定、质因数分解、欧拉函数计算）时，需要一个快速验证工具。本工具的 Miller-Rabin 算法能在毫秒级判断大数质数性，因式分解功能则能辅助验证分解结果的正确性，帮助选手在备赛阶段快速检验算法实现。
对比矩阵本工具 vs 竞品 vs 传统方法
| 维度 | 本工具 | 竞品 A (Wolfram|Alpha) | 传统方法 |
|---|---|---|---|
| 数据隐私 | 纯浏览器端计算，输入数据不上传服务器 | 输入发送至云端服务器处理 | 依赖人工或本地软件，无网络传输风险 |
| 处理速度 | 毫秒级响应（Miller-Rabin 概率测试） | 秒级，但受网络延迟影响 | 手工计算极慢（大数需数分钟至数小时） |
| 离线可用性 | 完全离线（页面加载后断网仍可用） | 必须联网 | 完全离线 |
| 输入大小限制 | 支持任意长度整数（受浏览器内存限制） | 付费版支持更大数，免费版有限制 | 受限于计算工具（如计算器位数）或人工耐心 |
| 功能范围 | 质数判定、区间质数列表、因式分解 | 质数判定、因式分解、数论函数、可视化等 | 仅质数判定或手工因式分解 |
| 收费模式 | 完全免费，无隐藏费用 | 免费版有功能限制，完整功能需订阅 | 免费（若使用开源软件或手工） |
| 结果确定性 | 概率性（Miller-Rabin 可调迭代次数） | 确定性算法（如 AKS） | 确定性（手工计算正确则无误） |
| 使用门槛 | 零学习成本，输入数字即出结果 | 需理解自然语言查询语法 | 需掌握质数判定算法或数学知识 |
使用指南
上手步骤 · 输入输出 · 避坑提示
输入输出示例7 个典型场景，覆盖常规、边界与易错
| 输入 | 输出 | 说明 |
|---|---|---|
| 17 | 是质数 | 典型场景：小质数，Miller-Rabin 快速判定 |
| 1000000007 | 是质数 | 典型场景：常用大质数（1e9+7），算法秒判 |
| 1 | 不是质数 | 边界 case：1 既非质数也非合数，易误判 |
| 2 | 是质数 | 边界 case：最小且唯一的偶质数 |
| 999999999989 | 是质数 | 边界 case：接近 1 万亿的大质数，算法仍准确 |
| 100 | 不是质数（因式分解：2² × 5²） | 易错 case：末尾为 0 的合数，新手误以为质数 |
| 0 | 不是质数 | 易错 case：0 无意义，用户可能误输入 |
常见错误对照8 个常踩的坑 · 错误 → 修复
1. 输入非整数（小数 / 科学计数法 / 文本）
错误
3.14 或 1e6 或 abc修复
17 或 9973质数判断只接受十进制整数。小数、科学计数法、字母都会被解析为 NaN 或非整数，工具无法处理。
2. 输入超过 2^53 的整数（JS 精度丢失）
错误
9007199254740993修复
9007199254740991浏览器端 JavaScript 的 Number 类型在 > 2^53 时无法精确表示每个整数，Miller-Rabin 检测会基于错误值给出不可靠结果。
3. 把 1 当作质数
错误
1修复
2 或 31 既不是质数也不是合数。数学定义要求质数有恰好两个正因数（1 和自身），而 1 只有一个因数。
4. 把负数的绝对值当作质数判断
错误
-7修复
7质数定义在正整数范围内。负数输入时工具可能报错或返回非质数，应先取绝对值再判断。
5. 区间查询时起始值大于结束值
错误
从 100 到 50修复
从 50 到 100区间质数表要求 start ≤ end。若颠倒顺序，工具可能返回空列表或报错，不会自动交换。
6. 因式分解时输入 0
错误
0修复
120 没有质因数分解（因数无穷多），工具无法处理。因式分解仅对正整数（≥2）有意义。
7. 认为 Miller-Rabin 一次检测 100% 正确
错误
只用一次基 a=2 就判定 2047 是质数修复
使用多个随机基（如 a=2,3,5,7）或选择确定性基组Miller-Rabin 是概率算法。2047 = 23×89，但以 a=2 检测会误判为质数（强伪质数）。工具内部已用多基降低错误率，但极端情况仍存在。
8. 把合数 1 当作质数输入因式分解
错误
1修复
2 或 12因式分解仅对 ≥2 的整数有意义。输入 1 时工具应返回空列表或提示不可分解。
工作原理
公式推导 · 流程图解 · 依据出处
核心公式
n = a^d \mod n \quad \text{(若结果 ≠ 1 且 ≠ n-1，则平方检测)}
变量说明
n— 待判断的奇数（≥3）a— 随机底数（2 ≤ a ≤ n-2）d— n-1 分解为 2^s × d 中的奇数部分s— n-1 中因子 2 的指数
示例
判断 n=221 是否为质数。n-1=220=2^2×55，故 s=2, d=55。取 a=174，计算 174^55 mod 221 = 47 ≠ 1 且 ≠ 220。平方得 47^2 mod 221 = 220 = n-1，通过本轮检测。换 a=137，137^55 mod 221 = 188 ≠ 1 且 ≠ 220，平方得 188^2 mod 221 = 205 ≠ 220，故 221 为合数（实际 221=13×17）。
适用范围
Miller-Rabin 概率性素性测试，适用于任意大奇数。对 n<2^64，取固定底数集 {2,3,5,7,11,13,17} 可保证确定性结果；对更大数需多次随机底数以降低误判概率（误判率 < 4^(-k)，k 为测试轮数）。
原理图
用户输入
本地处理（浏览器内）
输出结果
开发者集成
3 种主流语言 · 复制即用
import random
# Miller-Rabin 素性测试（确定性版本，适用于 64 位整数）
def is_prime(n: int) -> bool:
if n < 2:
return False
# 小素数快速筛除
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
for p in small_primes:
if n % p == 0:
return n == p
# 将 n-1 写成 d * 2^s
d, s = n - 1, 0
while d % 2 == 0:
d //= 2
s += 1
# 对 64 位整数，以下 7 个基足以保证确定性
for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
if a % n == 0:
continue
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
# 示例
print(is_prime(1000000007)) # True（大质数）
print(is_prime(1000000009)) # True
print(is_prime(1000000008)) # Falsepackage main
import (
"fmt"
"math/big"
)
// 使用 math/big 的 ProbablyPrime（Miller-Rabin 实现）
func isPrime(n int64) bool {
if n < 2 {
return false
}
// 小素数快速过滤
smallPrimes := []int64{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
for _, p := range smallPrimes {
if n%p == 0 {
return n == p
}
}
// big.Int 的 ProbablyPrime 使用 Miller-Rabin，20 次迭代错误率 < 4^-20
bigN := big.NewInt(n)
return bigN.ProbablyPrime(20)
}
func main() {
fmt.Println(isPrime(1000000007)) // true
fmt.Println(isPrime(1000000009)) // true
fmt.Println(isPrime(1000000008)) // false
}// Miller-Rabin 确定性版本（适用于 < 2^64 的整数）
function isPrime(n) {
if (n < 2) return false;
const smallPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
for (const p of smallPrimes) {
if (n % p === 0) return n === p;
}
// 将 n-1 写成 d * 2^s
let d = n - 1, s = 0;
while (d % 2 === 0) {
d /= 2;
s++;
}
// 对 64 位整数，以下 7 个基保证确定性
const bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];
for (const a of bases) {
if (a % n === 0) continue;
let x = BigInt(a) ** BigInt(d) % BigInt(n);
if (x === 1n || x === BigInt(n) - 1n) continue;
let cont = false;
for (let i = 0; i < s - 1; i++) {
x = (x * x) % BigInt(n);
if (x === BigInt(n) - 1n) {
cont = true;
break;
}
}
if (!cont) return false;
}
return true;
}
// 示例（注意：JavaScript 的 Number 只能安全表示 2^53 以内的整数）
console.log(isPrime(1000000007)); // true
console.log(isPrime(1000000009)); // true
console.log(isPrime(1000000008)); // false常见问题
7 个高频疑问
这个质数判断工具怎么用？输入一个数点一下就行吗？
对。在输入框里填一个整数（比如 97），点击「判断」按钮，结果区会显示「是质数」或「不是质数」。如果要分解因数，选「因式分解」模式，输入合数后会列出所有质因子。如果要查某个区间内有多少质数，选「区间质数表」，填起始和结束数字（如 1 到 100），结果会列出该区间所有质数并统计个数。所有操作都在当前页面完成，不需要刷新。
我输入一个很大的数（比如 20 位），为什么判断结果出来很快？会不会是猜的？
这个工具用的是 Miller-Rabin 概率性素性测试，不是逐个试除。对于 20 位以内的整数，取 10 个随机基底的 Miller-Rabin 测试，错误概率低于 2^{-20}（约百万分之一），而且测试在浏览器内 JavaScript 执行，纯 CPU 计算，不需要网络请求，所以 20 位数 1-2 秒就出结果。如果输入的数小于 2^32（约 43 亿），工具会自动切换到确定性试除，结果 100% 准确。大于 43 亿的数会提示「概率性测试结果」，结果仅供参考。
为什么我输入 1 或 0，工具说不是质数？1 不是质数吗？
根据数学定义，质数必须大于 1 且只有 1 和自身两个正因数。1 只有一个正因数（1），所以不是质数，也不是合数。0 有无限多个因数，同样不是质数。这个定义是数学界的共识（算术基本定理要求质数从 2 开始），工具严格按照这个定义判断。如果你输入负数或小数，工具会提示「请输入大于 1 的整数」。
因式分解结果里的数字是怎么来的？比如 84 = 2^2 × 3 × 7，这个 2^2 是什么意思？
因式分解是把一个合数拆成质数的乘积。2^2 表示 2 的 2 次方，即 2 × 2。84 = 2 × 2 × 3 × 7 = 2^2 × 3 × 7。工具先用试除法从小质数（2、3、5、7...）开始除，除到不能整除为止，然后记录每个质数出现的次数并用指数表示。如果你看到 2^2 × 3 × 7，意思是 84 的质因子有 2（出现 2 次）、3（1 次）、7（1 次）。
我输入了 999999999999999999（18 个 9），页面卡住了，是不是工具坏了？
不是工具坏了，是数字太大了。Miller-Rabin 测试对 18 位数仍然能算，但 JavaScript 处理超过 15 位的整数时，数字会进入「双精度浮点数」范围，部分大整数运算会丢失精度。工具对超过 2^53（约 9007199254740992）的整数会弹出警告「精度可能不足」。如果你输入的数是 2^53 以内，工具能正常处理；超过这个范围，建议分拆成多位小数或使用专门的素数测试软件。
这个工具和百度上搜到的「质数判断在线」有什么区别？哪个准？
核心区别在于算法和隐私。本工具用 Miller-Rabin 概率性测试（大数）配合试除（小数），所有计算在浏览器内完成，不把数据发到服务器。部分在线工具用后端 API 判断，输入的数字会经过网络传输，存在隐私风险（比如你输入的是密码相关的大质数）。准确度方面：对于 2^32 以内的数，本工具 100% 准确；更大的数有百万分之一误判概率。其他工具如果不公开算法，无法判断其准确率。
我用区间质数表查 1 到 10000，结果出来很慢，等了 10 秒，有没有办法快点？
区间质数表用的是埃拉托色尼筛法（Sieve of Eratosthenes），需要遍历区间内的每个数并标记合数。区间越大（比如 1 到 10000），筛法要处理的数越多，计算时间越长。10000 以内大约 0.5-1 秒，如果你感觉等了 10 秒，可能是浏览器性能较低或开启了太多标签页。可以缩小区间（比如先查 1 到 1000，再查 1001 到 2000）分多次查询。另外，工具是纯前端计算，不依赖网络，换个性能好的浏览器（Chrome/Edge）会快很多。