GCD of Two Numbers in Python

June 29, 2023

GCD of Two numbers in Python

Here, in this section, we will discuss the GCD of two numbers in python. Basically, the GCD (Greatest Common Divisor) or HCF (highest common factor ) of two numbers is the largest positive integer that divides each of the integers where the user entered number should not be zero.

GCD

What's on the Page

  • Method 1: Linear Quest to find GCD
  • Method 2: Euclidean Algorithm: Repeated Subtraction
  • Method 3: Recursive Euclidean Algorithm: Repeated Subtraction
  • Method 4: Modulo Recursive Euclidean Algorithm: Repeated Subtraction
  • Method 5: Handling Negative Numbers in GCD

Method 1 : Linear Quest

Algorithm

  • Initialize GCD = 1
  • Run a loop in the iteration of (i) between [1, min(num1, num2)]
  • Note down the highest number that divides both num1 & num2
  • If i satisfies (num1 % i == 0 and num2 % i == 0) then new value of GCD is i
  • Print value of GCD

Method 1 : Python Code

Run 
num1 = 36
num2 = 60
gcd = 1

for i in range(1, min(num1, num2)):
    if num1 % i == 0 and num2 % i == 0:
        gcd = i
print("GCD of", num1, "and", num2, "is", gcd)

Output

GCD of 36 and 60 is 12

Lowest Common Multiple (LCM)

 

Binary to Decimal to conversion

Octal to Decimal conversion

Hexadecimal to Decimal conversion

Method 2 : Repeated Subtraction

Algorithm

  • Run a while loop until num1 is not equals to num2
  • If num1>num2 then num1 = num1 – num2
  • Else num2 = num2 – num1
  • After the loop ends both num1 & num2 stores GCD

Method 2 : Python Code

Run 
num1 = 36
num2 = 60
a = num1
b = num2

while num1 != num2:
    if num1 > num2:
        num1 -= num2
    else:
        num2 -= num1

print("GCD of", a, "and", b, "is", num1)

Output

GCD of 36 and 60 is 12

Method 3 : Repeated Subtraction using Recursion

Algorithm

  • Checked whether any of the input is 0 then return sum of both numbers
  • If both input are equal return any of the two numbers
  • If num1 is greater than the num2 then Recursively call findGCD(num1 – num2, num2)
  • Else Recursively call findGCD(num1, num2-num1)

Method 3 : Python Code

Run 
# Recursive function to return GCD of two number
def findGCD(num1, num2):
    
    # Everything divides 0
    if num1 == 0 or num2 == 0:
        return num1 + num2
    
    # base case
    if num1 == num2:
        return num1
    
    # num1>num2
    if num1 > num2:
        return findGCD(num1 - num2, num2)
    else:
        return findGCD(num1, num2 - num1)


num1 = 36
num2 = 60

print("GCD of", num1, "and", num2, "is", findGCD(num1, num2))

Output

GCD of 36 and 60 is 12

Method 4 : Repeated Subtraction with Modulo Operator using Recursion

Algorithm

  • If b is equals to 0 return a
  • Else recursively call the function for value b, a%b and return 

Method 4 : Python Code

Run 
# This method improves complexity of repeated subtraction
# By efficient use of modulo operator in euclidean algorithm
def getGCD(a, b):
    return b == 0 and a or getGCD(b, a % b)


num1 = 36
num2 = 60

print("GCD of", num1, "and", num2, "is", getGCD(num1, num2))

Output

GCD of 36 and 60 is 12

Method 5 : Handling Negative Numbers in GCD

Algorithm

If any of the number is negative then convert it to positive by multiplying it with -1 as according to the proper definition GCD of two numbers can never be negative.

  • If b is equals to 0 return a
  • Else recursively call the function for value b, a%b and return 
Run 
# This method improves complexity of repeated subtraction
# By efficient use of modulo operator in Euclidean algorithm
def getGCD(a, b):
    return b == 0 and a or getGCD(b, a % b)


num1 = -36
num2 = 60

# if user enters negative number, we just changing it to positive
# By definition GCD is the highest positive number that divides both numbers
# -36 & 60 : GCD = 12 (as highest num that divides both)
# -36 & -60 : GCD = 12 (as highest num that divides both)
num1 >= 0 and num1 or -num1
num2 >= 0 and num2 or -num2

print("GCD of", num1, "and", num2, "is", getGCD(num1, num2))

Method 5 : Python Code

Output

GCD of -36 and 60 is 12

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Working with Numbers

5 comments on “GCD of Two Numbers in Python”


  • Archan

    A = int(input())
    B = int(input())
    for i in range(A, 0, -1):
    if A % i == 0:
    if B % i == 0:
    print(i, end=””)
    exit()


  • Sonal

    num1=int(input(“Enter the 1st number “))
    num2=int(input(“Enter the 2nd number “))
    l=[]
    n=min(num1,num2)+1
    for i in range(1,n):
    if num1%i==0 and num2%i==0:
    l.append(int(i))
    else:
    continue
    hcf=max(l)
    print(“{} is the HCF of {} and {}”.format(hcf,num1,num2))


  • Joyan

    def gcd(a,b):
    if b == 0 :
    return a
    return gcd(b,a % b)

    a, b = [int(x) for x in input().split()]
    res = []
    res.append(gcd(a,b))
    print(res)


  • Gorgulls

    Another easier way is ::
    import fractions
    a=int(input(“Enter the first number:”))
    b=int(input(“Enter the second number:”))
    print(“The GCD of the two numbers is”,fractions.gcd(a,b))


  • Daily

    a=int(input(“Enter no.:”))
    b=int(input(“Enter no.:”))

    l1=[]
    l2=[]
    l3=[]
    l4=[]
    def factors(n,l):
    for i in range(1,n+1):
    if n%i==0:
    l.append(i)

    def GCD(l1,l2,l3,l4):
    factors(a,l1)
    factors(b,l2)
    print(l1)
    print(l2)
    l4 = list(set(l1) & set(l2)) # intersection between 2 list
    l4.sort()
    print(“GCD: “,l4[-1])

    GCD(l1,l2,l3,l4)