Greatest Common Denominator counter [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I wanted to make a greatest common divisor counter in python, but I'm not exactly sure how to go at it, or where to start... Pretty much all I've got is this equation (a and b are numbers):

a = b * quotient + remainder

And I want the counter to print all the steps until remainder is lower than a, and then show the GCD.

I've also searched some more and found out that quotient of 2 numbers can be simply done with the // command and remainder with % command, so basically:

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

I'm also aware that I need a loop for the counter, but I've got no idea how to go about that... Help would be most appreciated.

I've seen some codes for GCD, but couldn't find one that would show all the steps.

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))

(the result would be the last step, which you can access by taking the last element of the list: steps[-1])

Output:

3725 -> 900 -> 125 -> 25