最大公约数（Python）

目录

质因数分解法

短除法

辗转相除法

更相减损法

---

最大公约数是指两个或多个整数共有约数中最大的一个。两个数 a 和 b 的最大公约数 (Greatest Common Divisor) 是指同时整除 a 和 b 的最大因子，记为 gcd (a, b) 。特殊的，当 gcd (a, b) = 1 ，我们称 a 和 b 互素。例如，1，2，4 均为 8 和 12 的公约数，最大的公约数就是 4。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。

两个正整数的乘积=最大公约数*最小公倍数

质因数分解法

质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的 最大公约数 。例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。

把几个数先分别分解质因数，再把各数中的全部公有的质因数和独有的质因数提取出来连乘，所得的积就是这几个数的 最小公倍数 。例如：求6和15的 最小公倍数 。先分解质因数，得6=2×3，15=3×5，6和15的全部公有的质因数是3，6独有质因数是2，15独有的质因数是5，2×3×5=30，30里面包含6的全部质因数2和3，还包含了15的全部质因数3和5，且30是6和15的公倍数中最小的一个，所以 [6，15]=30。

短除法

短除法：短除法求最大公约数，先用这几个数的公约数连续去除，一直除到所有的商互质为止，然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。短除法求 最小公倍数 ，先用这几个数的公约数去除每个数，再用部分数的公约数去除，并把不能整除的数移下来，一直除到所有的商中每两个数都是 互质 的为止，然后把所有的除数和商连乘起来，所得的积就是这几个数的最小公倍数。例如：求12、15、18的最小公倍数。

所以 [12,15,18]=2×3×5×2×3=180。

短除法的本质就是质因数分解法，只是将质因数分解用短除符号来进行。短除符号就是除号倒过来。短除就是在除法中写 除数 的地方写两个数共有的 质因数 ，然后落下两个数被公有质因数整除的商，之后再除，以此类推，直到结果 互质 为止（两个数互质）。而在用短除计算多个数时，对其中任意两个数存在的因数都要算出，其它没有这个 因数 的数则原样落下。直到剩下每两个都是互质关系。求最大公因数便乘一边，求 最小公倍数 便乘一圈。

辗转相除法

辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

方法是：以小数除大数，如果能整除，那么小数就是所求的最大公约数。否则就用余数来除除数；再用新除法的余数去除刚才的余数。依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。
具体过程如下：
输入正整数 m 和 n ，保证 m 不小于 n ;
如果 n ≠0，则求 r = m % n ，然后 m = n , n = r ;重复此操作直到 n =0;
如果 n =0，则此时 m 就是最大公约数。

例如：求4453和5767的最大公约数时，可作如下除法．
5767÷4453=1余1314
4453÷1314=3余511

1314÷511=2余292
511÷292=1余219
292÷219=1余73
219÷73=3
于是得知，5767和4453的最大公约数是
73.
若要求这两个数的最小公倍数，其值就是这两数之积除以这两数的最大公约数得到的商。

例如，求（319，377）：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58）

∴（377，319）=（319，58）；

∵ 319÷58=5（余29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0）

∴ （58，29）= 29；

∴ （319，377）=29。

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

x = int(input('请输入第一个正整数:'))
y = int(input('请输入第二个正整数:'))
m = max(x,y)            #找出x,y中的最大值
n = min(x,y)            #找出x,y中的最小值
r = m%n                 #求得最大值除以最小值后的余数
 
while r!=0:             #如果余数不等0,则进行以下循环
    m =n                #把最小值赋给m
    n =r                #把余数赋给n
    r = m%n             #求得最大值除以最小值后的余数
 
print('这两个数的最大公约数为:',n)
input("运行完毕,请按任意键退出....")

"""
枚举法:通过枚举从小到大的所有可能的约数，并判断是否同时是两数的约数，从而找出最大公约数。
"""
def gcd(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
 
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i
 
    return 1
 
 
data1 = int(input('输入第一个数: '))
data2 = int(input('输入第二个数: '))
 
print('最大公约数为：', gcd(data1, data2))

import random
 
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 
data1 = int(input('输入第一个数: '))
data2 = int(input('输入第二个数: '))
 
print('最大公约数为：', gcd(data1, data2))

"""
math库的gcd()
"""
import math
 
def gcd(a, b):
    return math.gcd(a, b)
 
data1 = int(input('输入第一个数: '))
data2 = int(input('输入第二个数: '))
print('最大公约数为：', gcd(data1, data2))

更相减损法

更相减损法：也叫 更相减损术 ，是出自《九章算术》的一种求最大公约数的算法，它原本是为 约分 而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“ 更相减损术 ”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫 等值算法 。

比较辗转相除法与 更相减损术 的区别

（1）都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

（2）辗转相除法适用于任何两个整数的最大公约数的求解，而更相减损术只适用于两个正整数的最大公约数的求解。