Euclidean Algorithm / GCD in Python

python

Solution

a = int(input("What's the first number? "))
b = int(input("What's the second number? ")) 
r=a%b
while r:
    a=b
    b=r
    r=a%b
print('GCD is:', b)

or use `break` in loop:

a = int(input("What's the first number? "))
b = int(input("What's the second number? ")) 
while 1:
    r=a%b
    if not r:
        break
    a=b
    b=r
print('GCD is:', b)

Problem

I'm trying to write the Euclidean Algorithm in Python. It's to find the GCD of two really large numbers. The formula is a = bq + r where a and b are your two numbers, q is the number of times b divides a evenly, and r is the remainder. I can write the code to find that, however if it the original numbers don't produce a remainder (r) of zero then the algorithm goes to step 2 => b = rx + y. (same as the first step but simply subbing b for a, and r for b) the two steps repeat until r divides both a and b evenly. This is my code, I haven't yet figured out how to do the subbing of values and create a loop until the GCD is found. ``` a = int(input("What's the first number? ")) b = int(input("What's the second number? ")) r = int(a - (b)*int(a/b)) if r == 0: print("The GCD of the two choosen numbers is " + str(b)) elif r != 0: return b and r (b == a) and (r == b) print("The GCD of the two numbers is " + str(r)) ```

Original source