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