python辗转相除法求最大公约数并输出循环次数

#使用辗转相除法，求两个整数的最大公约数gcd。这两个整数是120和168，打印输出最终结果以及循环次数。

a=int(input("a="))
b=int(input("b="))
if a>b:
    #计算循环次数
    count=0
    #进行辗转相除
    while a%b != 0:
        p=a%b
        a=b
        b=p
        count=count+1
    print("a和b的最大公约数是：{}\n循环次数是：{}\n".format(b,count+1))
else:
    #计算循环次数
    count=0
    #进行辗转相除
    while b%a != 0:
        p=b%a
        b=a
        a=p
        count=count+1
    print("a和b的最大公约数是：{}\n循环次数是：{}\n".format(a,count+1))

# 循环次数
count = 0


def get_gcd(m, n):
    global count
    count += 1
    value = m % n if m > n else n % m
    min_value = min(m, n)
    if value == 0:
        return min_value
    else:
        return get_gcd(value, min_value)


print(f"最大公约数gcd为：{get_gcd(120, 168)}")
print(f"循环次数为：{count}")

运行结果：

最大公约数gcd为：24
循环次数为：3

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7551800
• 除此之外, 这篇博客: python实现GCD算法中的 3 评估结果 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 计算两个随机数的最大公约数，比较四种算法的循环次数、耗时。

  辗转相除法、更相减损术的效率远高于穷举法，且这两个方法的计算规模几乎不受计算对象量级的影响。

  辗转相除法的效率最高，更相减损术次之。除穷举法的效率高于减穷举法。