质数计算器

质数判定 · 质因数分解 · 质数生成

输入数字

指南

了解更多

什么是质数（Prime Number）？

质数是指大于 1、且除了 1 和它本身以外没有其他约数的自然数。2、3、5、7、11、13... 等都是质数，除 2 以外的所有质数都是奇数。质数是数学的基本组成单元，被称为「数的原子」。

埃拉托斯特尼筛法

这是公元前 240 年左右由希腊数学家埃拉托斯特尼发明的寻找质数的算法。从 2 开始，依次划去每个质数的倍数，从而高效地找出质数。

孪生质数

相差为 2 的一对质数称为孪生质数。例如 (3,5)、(5,7)、(11,13)、(17,19) 等，孪生质数是否有无穷多对，至今仍是一个未解之谜。

质数的应用

• RSA 加密：利用大质数相乘容易、而质因数分解困难的特性 • 哈希函数：使用质数来确定哈希表的大小 • 随机数生成：利用质数生成伪随机数 • 周期计算：蝉的生命周期为质数年的原因

质数的定义与历史

质数（Prime Number）是指大于 1、且除了 1 和它本身以外没有其他约数的自然数。最小的质数是 2，也是唯一的偶数质数。2、3、5、7、11、13、17、19、23、29... 如此继续下去。古希腊数学家欧几里得在公元前 300 年左右证明了「质数有无穷多个」。质数在数学中扮演着极其重要的角色，被称为「数的原子（atoms of numbers）」。根据算术基本定理（Fundamental Theorem of Arithmetic），每个大于 1 的自然数都可以唯一地表示为若干质数的乘积。例如 60 = 2² × 3 × 5，360 = 2³ × 3² × 5。这就好比所有物质都由原子构成一样，所有的数都由质数构成。

质数判定算法

判定某个数 n 是否为质数，最简单的方法是用 2 到 n-1 的所有数去除，但这非常低效。改进的方法是只检查 2 到 √n。因为当 n = a × b 时，必然有 a ≤ √n 或 b ≤ √n 成立。例如要判断 101 是否为质数，由于 √101 ≈ 10.05，只需检查 2、3、5、7 即可。更高效的米勒-拉宾（Miller-Rabin）概率性质数判定法，即使对非常大的数也能快速判定。AKS 质数判定法是 2002 年发现的第一个多项式时间的确定性算法。现代密码学需要处理数百位的质数，因此高效的质数判定至关重要。

埃拉托斯特尼筛法：质数生成算法

埃拉托斯特尼筛法（Sieve of Eratosthenes）是公元前 240 年左右由希腊数学家埃拉托斯特尼发明的寻找质数的算法。步骤如下：① 列出 2 到 n 的所有数。② 2 是质数，标记它，并划去 2 的所有倍数（4、6、8、10...）。③ 下一个未被划去的数 3 是质数，标记它，并划去 3 的所有倍数（6、9、12、15...）。④ 下一个未被划去的数 5 是质数，标记它，并划去 5 的所有倍数。⑤ 将此过程重复到 √n 为止。⑥ 剩下的所有数都是质数。例如找出 30 以内的质数即为：2、3、5、7、11、13、17、19、23、29。该算法的时间复杂度为 O(n log log n)，非常高效。可以在几秒钟内找出 100 万以内的所有质数。

质因数分解的原理与应用

质因数分解（Prime Factorization）是指将某个数表示为若干质数乘积的过程。根据算术基本定理，每个大于 1 的自然数都有唯一的质因数分解。质因数分解方法：① 从最小的质数 2 开始，检查是否能整除。② 若能整除，就继续用 2 去除。③ 当不能再被 2 整除时，尝试下一个质数 3、5、7...。④ 重复直到商为 1。示例：将 360 质因数分解，360 ÷ 2 = 180，180 ÷ 2 = 90，90 ÷ 2 = 45，45 ÷ 3 = 15，15 ÷ 3 = 5，5 ÷ 5 = 1。因此 360 = 2³ × 3² × 5。质因数分解的应用：计算最大公约数和最小公倍数、约分分数、RSA 加密的安全性基础。大数难以进行质因数分解，正是现代密码学的核心。

孪生质数与哥德巴赫猜想

孪生质数（Twin Primes）是相差为 2 的一对质数。例如 (3, 5)、(5, 7)、(11, 13)、(17, 19)、(29, 31)、(41, 43)... 等。孪生质数猜想（Twin Prime Conjecture）主张「存在无穷多对孪生质数」，但至今仍是数学中尚未证明的未解难题之一。2013 年，张益唐（Yitang Zhang）证明了相差不超过 7000 万的质数对有无穷多对，此后经过合作研究，将这一间隔缩小到了 246。哥德巴赫猜想（Goldbach Conjecture）主张「每个大于 2 的偶数都可以表示为两个质数之和」。示例：4=2+2、6=3+3、8=3+5、10=3+7=5+5、100=3+97=11+89。该猜想于 1742 年提出，但至今仍未被证明。目前已用计算机验证到 4×10¹⁸。

RSA 加密与质数的实际应用

RSA 加密是互联网安全的核心技术，它利用了大质数相乘容易、而质因数分解困难这一数学性质。RSA 密钥生成过程：① 选择两个大质数 p、q（各自 1024 位以上）。② 计算 n = p × q（公钥的一部分）。③ 计算 φ(n) = (p-1)(q-1)。④ 选择与 φ(n) 互质的公开指数 e（通常为 65537）。⑤ 计算满足 e × d ≡ 1 (mod φ(n)) 的私密指数 d。公钥为 (n, e)，私钥为 (n, d)。加密：C = M^e mod n，解密：M = C^d mod n。若能将 n 质因数分解求出 p 和 q，就能计算出私钥 d，但对数百位的数进行质因数分解，即使用当今的计算机也实际上无法完成（需要数百万年）。质数的其他应用：将哈希表大小设为质数可减少冲突；蝉的 13 年、17 年生命周期是为了让周期不与捕食者重叠而进化出来的；音乐的节奏型中会使用质数节拍。

常见问题

质数最大可以判定到多少？

本工具支持对 1 到 10,000,000 的数字进行质数判定和质因数分解，而质数生成与孪生质数查找则在 2~100,000 的范围内运行。

为什么质数会被用于加密？

将两个大质数相乘很容易，但要把它们的乘积重新质因数分解却非常困难。RSA 加密正是利用了这种不对称性来保护互联网通信。