质因数分解计算器

什么是质因数分解计算器？

质因数分解就是把一个合数写成若干素数（质数）的乘积，例如 360 = 2³ × 3² × 5。算术基本定理保证：每个大于 1 的整数都有唯一一种分解方式（不计顺序），就像化学里每种物质有唯一的分子式。素数是只有 1 和自身两个约数的整数（2、3、5、7、11……），它们是整数世界的「原子」。

找素数最古老的方法是**埃氏筛**（埃拉托斯特尼筛法）：从 2 开始，把每个素数的倍数全部划掉，剩下的就是素数。判定一个大数是否素数则依赖米勒-拉宾检验——7 个特定底数即可对工程范围内的整数给出确定性结论，这正是本工具处理 19 位大整数的底气。

有了分解式 n = p₁^a₁ × p₂^a₂ × …，一组经典数论函数立刻可得：约数个数 τ(n) = (a₁+1)(a₂+1)…，约数和 σ(n) = ∏(pᵢ^(aᵢ+1)−1)/(pᵢ−1)，欧拉函数 φ(n) = n∏(1−1/pᵢ) 表示「不超过 n 且与 n 互质的整数个数」——它是 RSA 加密的数学基石，分解大整数的困难性撑起了整个现代密码体系。

1742 年哥德巴赫猜想「每个大于 2 的偶数都是两个素数之和」，至今未证，目前最好的成果是陈景润 1966 年的「1+2」。本工具可验证 100 万以内任何偶数的全部素数拆分，并画出「哥德巴赫彗星」图。

完全数（σ(n) = 2n，如 6、28、496）与梅森素数（2ᵖ−1）通过欧几里得-欧拉定理一一对应：每当 2ᵖ−1 是素数，2^(p−1)(2ᵖ−1) 必为完全数。人类迄今只发现 52 个梅森素数，最大的有 4100 多万位。

如何使用质因数分解计算器

1. 1

   选择功能模式：质因数分解、素数判定、素数表、哥德巴赫验证或特殊数查询。

2. 2

   质因数分解：输入 2 – 1 万亿之间的整数，点击计算，得到标准分解式、因子树、短除法步骤与 τ/σ/φ 等数论函数。

3. 3

   素数判定：输入最大 19 位的整数，判定是否素数；素数给出它是第几个（百万以内）与类型标注，合数给出最小素因子与完整分解。

4. 4

   素数表：生成前 N 个素数、区间素数或孪生素数对，附素数定理密度对照；前 100 个以内显示埃氏筛网格图。

5. 5

   哥德巴赫验证：输入 4 – 100 万的偶数，列出全部「素数+素数」拆分，并用彗星图展示拆分数量随偶数增长的波动。

6. 6

   特殊数：判定完全数/过剩数/亏损数、查找亲和数、检验梅森数 2ᵖ−1 的素性、列出回文素数表。

计算示例

注意事项

• 1 既不是素数也不是合数。若承认 1 是素数，分解唯一性立刻崩溃（6 = 2×3 = 1×2×3 成了两种分解），所以数学家特意把它排除——素数定义里「恰好两个正约数」这句话就是为此设计的。

• 2 是唯一的偶素数，也是最特殊的素数：所有其他素数都是奇数，因此两个奇素数之和必为偶数（哥德巴赫拆分的两端除了含 2 的情形外都是奇素数）。孪生素数如 (3,5)、(11,13) 也只在奇数中存在。

• 本工具的素数判定分两档：1 万亿以内用试除法直接给全部分解；1 万亿到 19 位用米勒-拉宾检验——对 [2, 325, 9375, 28178, 450775, 9780504, 1795265022] 这 7 个底数通过检验的 64 位内整数必为素数，这是数学证明的结论而非概率。

• 试除法有明确的能力边界：分解超过 1 万亿的整数可能需要天文数字的时间，这正是 RSA 加密的安全基础——2048 位的大数连超级计算机也分解不动，但验证两个大素数的乘积却瞬间完成。「乘法容易分解难」是密码学最依赖的不对称性。

• 卡迈克尔数是「伪装的合数」：561 = 3×11×17 对所有与它互素的底数都能通过费马小定理检验（a⁵⁶⁰ ≡ 1 mod 561），是最小的卡迈克尔数。米勒-拉宾检验通过更强的条件识破它们——561 在底数 2 下立刻现形。这也说明「单凭一个底数判素」是不可靠的。

• 哥德巴赫彗星的波动不是噪声：拆分数量的「峰」出现在 6 的倍数附近（如 210、330），「谷」出现在 ±1 型素数密集处。原因是若 n 被 3 整除，p ≡ 1 (mod 3) 与 p ≡ 2 (mod 3) 的素数都能配对；否则只有一半素数有资格参与。群论结构决定了彗星的轮廓。

• 梅森数 2ᵖ−1 为素数的必要条件是 p 本身为素数（若 p = ab 则 2ᵃ−1 整除 2ᵖ−1），但不充分：11 是素数，2¹¹−1 = 2047 = 23×89 却是合数。所以每个梅森素数的发现都是新闻——目前最大的 2⁸²⁵⁸⁹⁹³³−1 有 2486 万位，由 GIMPS 分布式项目 2018 年找到。

• 回文素数（正读反读相同，如 131、929）有个漂亮的定理：除了 11 以外，所有回文素数都有奇数位数——任何偶数位回文数必被 11 整除（交错和判定法）。所以两位回文素数不存在，四位的也不存在，找它们只需看奇数位。

常见问题

参考资料

1. [1]Wikipedia：Prime number（素数）
2. [2]Wikipedia：Integer factorization（整数分解）
3. [3]Wikipedia：Sieve of Eratosthenes（埃氏筛法）
4. [4]Wikipedia：Goldbach 猜想（哥德巴赫猜想）
5. [5]Wikipedia：Euler 函数（欧拉 totient 函数）
6. [6]Wikipedia：Perfect number（完全数）