百科知识网

求最大公因数的四种方法

发布时间：2025-10-07 | 来源：互联网转载和整理

1. 完全分解法：将两个数分解质因数，然后找出两个数共同的质因数，最后将这些共同的质因数相乘即为最大公因数。

2. 辗转相除法：辗转相除法也叫欧几里得算法，是求最大公因数的常用方法。具体操作如下：将两个数中大的数除以小的数，然后用小的数去除大的数所余的数，直到余数为0，此时的除数即为最大公因数。

3. 最大公因数定理：也称为欧几里得定理。定理内容为：两数的最大公因数等于其中较小的数和两数的差的最大公因数。例如：gcd(21, 15) = gcd(15, 6) = gcd(6, 3) = 3。

4. 短除法：具体操作是将两个数同时除以2，如果两个数都能整除2，则继续将它们同时除以2；如果其中一个数不是偶数，则将这个数除以它与另外一个数的最大公因数，而这个数本身又是偶数，所以可以继续将结果除以2。最终得到的两个奇数的积就是最大公因数。例如：求 340 和 196 的最大公因数：340 和 196 同时除以 2 得到 170 和 98，继续除以 2 得到 85 和 49，85 和 49 的最大公因数是 1，所以 340 和 196 的最大公因数是 2^2 * 1 = 4。