跳到正文

质因数分解与最大公约数

Factors, GCD & LCM

把整数做质因数分解,并对一个或多个数求最大公约数、最小公倍数、约数和素性。

把一个整数拆成质因数,并告诉你它的约数、约数和、欧拉 φ 函数和相邻的质数。改为给它几个数,它就计算最大公约数和最小公倍数。运算在任何大小下都是精确的,所以超过 2^53 的数也表现正常。

🔒 完全在你的浏览器里运行mathprimegcdnumber-theory

一个数

多大都可以。这里的运算全部是精确的整数运算,所以超过 2^53(电子表格从这里开始分不清相邻的整数)的数也能正确处理。

质因数分解

360 = 2^3 × 3^2 × 5

是质数吗

否

位数

3

约数个数

24

约数之和

1,170

欧拉 φ

96

比它小且与它互质的数的个数

是完全数吗

否

等于自身真约数之和

下一个质数

367

上一个质数

359

约数(24)

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360

多个数

最大公约数

6

最小公倍数

5,040

一行一个,或者用逗号分隔。

质数判定是证明,不是概率。米勒–拉宾在一般情况下是概率性检验,但以前 13 个质数为基时,已经证明在 3.3 × 10²⁴ 以下没有例外的合数 — 远远超出这里能输入的任何数。大的合数先做试除,再用 Pollard rho 拆开,两个十五位质数的乘积能在毫秒内分开正是因为这个。

怎么用

  1. 输入一个数

    数字,可以带逗号。分解结果、约数和是否为质数的结论一起出现。

  2. 或者几个数,求最大公约数和最小公倍数

    一行一个或用逗号分隔。约分一组分数或者算一个重复周期,要的就是这个面板。

  3. 需要质数时看相邻的

    显示下一个和上一个质数,当你想为哈希表或模数找一个特定大小附近的质数时,找的就是它。

常见问题

为什么它拒绝了一个大数?

判断一个数是否为质数在任何大小下都很快;拆开它才是昂贵的方向。Pollard 的 rho 算法运行时间大约是这个数的四次方根——二十位时是毫秒级,过了四十位就是好几秒,而且是在一次浏览器无法打断的调用里。它宁可停下来也不冻住标签页,但仍然会告诉你这个数是不是质数。

1 是质数吗?

按定义不是——质数恰好有两个不同的约数,而 1 只有一个。把它排除掉才使质因数分解唯一,这正是定义划在那里的全部理由。

欧拉 φ 函数是干什么的?

它数的是小于 n 且与 n 没有公因数的数的个数。它是模 n 乘法群的大小,这是 RSA 能成立的原因;当 n 与十互质时,它也是循环小数 1/n 的周期。

可以从这些接进来

接下来

这些工具吃得下当前工具的产出,结果可以直接送过去。