Python实现求解最大公约数的五种方法总结

a=int(input("please input the first number："))
b=int(input("please input the second number："))
m,n=a,b #  创建两个变量存储a和b
t=1 #  创建t作为最大公约数的载体
for i in range(2,min(a,b)):
    while (a%i==0 and b%i==0):
       t*=i #  所有公约数累乘起来
       a/=i
       b/=i
print((f"{m},{n}的最大公约数为：{t}"))

a=int(input("please input the first number："))
b=int(input("please input the second number："))
#  首先要给两数排序，保证大数除以小数
m=max(a,b)
n=min(a,b)
t=m%n
while t!=0:
    m,n=n,t #  仔细观察不难发现：每个除式的m、n是都是上一个式子的n和余数
    t=m%n #  更新余数
print(f"{a}和{b}的最大公约数为{n}")

def GCD(a,b):
    #  比较大小，保证大数除以小数
    if a<b:
        a,b=b,a
    #  判断是否能整除，若能整除，直接返回被除数
    if a%b==0:
        return b
    #  若不能整除，则返回函数GCD，参数做相应变化
    else:
        return GCD(b,a%b)
a=int(input("please input the first number："))
b=int(input("please input the second number："))
gcd=GCD(a,b)
print(f"{a}和{b}的最大公约数为{gcd}")

a=int(input("please input the first number："))
b=int(input("please input the second number："))
#  首先要给两数排序，保证大数减小数
m=max(a,b)
n=min(a,b)
#  判断两数是否都是偶数，如果都是偶数就同时除2
while m%2==0 and n%2==0:
    m,n=m/2,n/2
t=m-n
#  判断条件是减数和差相等
while n!=t:
    m,n=max(n,t),min(n,t) #  每减一轮之后，都要重新判断减数和差的大小，再次以大数减去小数
    t=m-n
print(f"{a}和{b}的最大公约数为{n}")

a=int(input("please input the first number："))
b=int(input("please input the second number："))
p,q=min(a,b),max(a,b)
lst=[]
for i in range(1,p+1):
    if p%i==0 and q%i==0:
        lst.append(i)
gcd=max(lst)
print(f"{a}和{b}的最大公约数为{gcd}")
 
#a=int(input("please input the first number："))
#b=int(input("please input the second number："))
#p,q=min(a,b),max(a,b)
#gcd=0
#for i in range(p,0,-1):
#    if p%i==0 and q%i==0:
#        gcd=i
#        break
#print(f"{a}和{b}的最大公约数为{gcd}")

def gcd_Stein(a, b):
    #  保证b比a小
    if a < b:
        a, b = b, a
    if (0 == b):
        return a
    #  a、b都是偶数，除2右移一位即可
    if a % 2 == 0 and b % 2 == 0:
        return 2 * gcd_Stein(a / 2, b / 2)
    #  a是偶数
    if a % 2 == 0:
        return gcd_Stein(a / 2, b)
    #  b是偶数
    if b % 2 == 0:
        return gcd_Stein(a, b / 2)
    #  都是奇数
    return gcd_Stein((a + b) / 2, (a - b) / 2)
 
a=int(input("please input the first number："))
b=int(input("please input the second number："))
gcd=int(gcd_Stein(a,b))
print(f"{a}和{b}的最大公约数为{gcd}")