6

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))
Improve this question
2

6 Answers 6

Reset to default
8 
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)
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

6

I think that's the shortest solution:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
Improve this answer

Comments

1

Try This 

a = int(input("Enter No.1"))

b = int(input("Enter No.2"))

r = a%b

q = int(a/b)

while(r!=0):

    a = b

    b = r

    q = int(a/b)

    r = a - (b * q)


print(b)
Improve this answer

Comments

1

I know this is old post but here it is:

def GCD(x , y):
    """This is used to calculate the GCD of the given two numbers.
    You remember the farm land problem where we need to find the 
    largest , equal size , square plots of a given plot?"""
    if y == 0:
        return x
    r = int(x % y)
    return GCD(y , r)

Taken from Algorithms 4th edition.

Note: if your numbers are REALLY REALLY large then try to increase the recursion limit by:

import sys
sys.seterecursionlimit("your new limit")

but be very very careful with it. I was able to fill my 12GB RAM and cause a freeze quite easily.

Improve this answer

Comments

1

I think there's one missing important condition for Euclidean Algorithm to work, which is a >= b > 0. So may I suggest this code I just made (quite long cuz I haven't viewed prev answers before building it haha.

def gcd(int1: int, int2: int):
# I used a recursive algorithm
# Condition: a>=b>0
if int1 < int2:
    a = int2
    b = int1
else:
    a = int1
    b = int2

if a % b == 0:
    return b
else:
    r = a % b
    gcd(b, r)
    return r
Improve this answer

Comments

1

I recently came across a question like this in my math class. The code I wrote was:

def EuclideanAlg(a,b):
    # switches the value of a and b if a is less than b
    if a <= b - 1:
        temp = a
        a = b
        b = temp
    # takes the remainder after a is divided by b
    r = a % b
    # iterates infinitely
    while True:
        # if a is divisible by b, b is the gcd of a,b
        if r == 0:
            return b
            break
        # a becomes the current value of b and b becomes the current value of r
        else:
            temp = r
            r = b % r
            b = temp
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.