python - 最大公分母计数器

Question

我想在 python 中做一个最大的公约数计数器，但我不完全确定如何去做，或者从哪里开始......我所拥有的几乎就是这个等式（a 和 b 是数字）：

a = b * quotient + remainder

我希望计数器打印所有步骤，直到余数低于 a，然后显示 GCD。

我还搜索了更多内容，发现两个数字的商可以简单地用 // 命令完成，余数用 % 命令完成，所以基本上：

a = b * (a // b) + (a % b)

我也知道我需要一个计数器的循环，但我不知道如何去做...帮助将不胜感激。

我看过一些 GCD 代码，但找不到能显示所有步骤的代码。

Answer 1

def gcd_steps(a, b):
    steps = []
    # this is the standard GCD finding algorithm;
    # we simply amend it with "step tracking"
    while b:
        # a, b = b, a % b
        tmp = a
        a = b
        b = tmp % b
        steps.append(a)
    return steps  # normally we'd want to return `a`
                  # but you want the steps not just the result

steps = gcd_steps(125 * 123 * 12314, 25 * 149)

# print the list with `->` between the steps
print(" -> ".join(str(x) for x in steps))

（结果将是最后一步，您可以通过获取列表的最后一个元素来访问它steps[-1]：）

输出：

3725 -> 900 -> 125 -> 25