最大公因数计算器

最大公因数（GCD/GCF）是能同时整除所有给定数的最大正整数。24 的因数 {1,2,3,4,6,8,12,24}、36 的因数 {1,2,3,4,6,9,12,18,36}，公共因数最大的是 12。分数约分（24/36 = 2/3）与化简比（24:36 = 2:3）的第一步永远是求 GCD。

辗转相除法（欧几里得算法，约公元前 300 年）是求 GCD 的神器：GCD(a,b) = GCD(b, a mod b)，反复取余直到余数为 0。GCD(36,24) = GCD(24,12) = GCD(12,0) = 12——两三步搞定。原理：a 与 b 的公因数必然也是 a−b（进而 a mod b）的因数，取余不改变公因数集合。它仍是现代密码学（RSA 密钥生成判互质）的底层组件。

GCD 与 LCM 是孪生兄弟：a×b = GCD(a,b) × LCM(a,b)。知道 GCD 就能秒算 LCM。两数 GCD = 1 时称互质（如 8 和 15）——互质不要求各自是素数，只要没有公共因子。互质是数论应用的关键状态：分数最简、RSA 选钥、中国剩余定理的前提都是互质。

最大公因数（GCD，也叫 GCF）的核心算法是欧几里得算法——人类历史上最古老的非平凡算法（约公元前 300 年《几何原本》记载）：GCD(a,b) = GCD(b, a mod b)，迭代到余数为 0。例：GCD(48,18)：48 = 18×2+12 → GCD(18,12)；18 = 12×1+6 → GCD(12,6)；12 = 6×2+0，得 6。它的效率极高，千位大数也只需几十步，至今仍是密码学（RSA 密钥生成）与计算数论的底层部件。

GCD 的典型应用：分数约分（24/36 同除以 GCD = 12 得 2/3）、「最大正方形地砖铺满长方形地面」类裁切问题（120×90 的地面最大方砖边长 = GCD(120,90) = 30 cm）、物品等分打包（48 个苹果和 36 个梨混装成相同果篮，最多 GCD(48,36) = 12 篮）。两个数 GCD 为 1 时称互质——这是最小公倍数速算（LCM = 乘积）与数论大量定理的前提条件。