最大公約數 · 最小公倍數 (含質因數分解)

輸入整數列表。計算器返回 GCD (歐幾里得演算法)、LCM、每個輸入的完整質因數分解。用 BigInt 處理任意大小的整數。

整數逗號、空格或換行分隔。至少 2 個。

最大公約數 (GCD)

最小公倍數 (LCM)

運作原理

兩個整數的 GCD 是能整除兩個數 (無餘數) 的最大整數。GCD(12, 18) = 6 因為 6 整除兩者且無更大數能。GCD(7, 13) = 1 因為它們無共同因子 (這種對稱為「互素」)。

我們用歐幾里得演算法: gcd(a, b) = gcd(b, a mod b), 遞迴。已知約 2300 年, 至今仍是最快的標準方法。三個或更多數: gcd(a, b, c) = gcd(gcd(a, b), c)。

LCM 是同時是兩個數倍數的最小正整數。LCM(4, 6) = 12 因為 12 是 4 和 6 都整除的第一個數。

公式: lcm(a, b) = (a × b) / gcd(a, b)。對 4 和 6: 24 / 2 = 12。三個數: lcm(a, b, c) = lcm(lcm(a, b), c)。

如果任何數是 0, LCM 是 0 (每個數都整除 0, 但「最小正」未定義)。計算器對該情況返回 0。

分數: 加 1/4 + 1/6, 求 LCM(4, 6) = 12 作公分母。1/4 = 3/12, 1/6 = 2/12, 和 = 5/12。

排程: 如果事件 A 每 4 天重複、事件 B 每 6 天, 它們每 LCM(4, 6) = 12 天同時發生。

密碼學: 基於 GCD 的演算法 (擴充套件歐幾里得) 是 RSA 金鑰生成和模逆元計算的基礎。

音樂理論: 週期 3 和 4 的節奏在 12 拍後同步 (LCM)。

›我的數互素時?

GCD = 1 且 LCM = 所有數的乘積。互素意味無共同質因子。

›可以包含負數?

可以。GCD/LCM 計算用絕對值。-12 和 18 給 GCD 6 和 LCM 36, 與 12 和 18 相同。

›如果輸入 0?

GCD(0, n) = |n| (因為每個整數整除 0, n 是該對最大)。LCM 與 0 按慣例是 0。全零 GCD/LCM 未定義。

›數能多大?

我們內部用 BigInt, 所以任意大小整數的算術都精確。實用極限是你的輸入速度和螢幕空間。

›為什麼質因數分解有用?

GCD = 共同質數乘積 (取較小指數)。LCM = 任何數中出現的所有質數的乘積 (取較大指數)。因數分解讓這些關係可見。

›GCD 與 LCM 的關係?

對兩個數: a × b = gcd(a, b) × lcm(a, b)。所以如果知道 {a, b, gcd, lcm} 中任意三個, 可以算第四個。不能幹淨推廣到三個或更多數。

›可以用於多項式 GCD?

本工具不能 — 我們僅處理整數。多項式用 SymPy 或 Maxima 等 CAS。

›資料會上傳嗎?

不會。計算在本地; 不向伺服器傳送。