# Python Program to find GCD of Two Numbers

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

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

### Method 5 : 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

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

### Output

`GCD of -36 and 60 is 12`

## Working with Numbers

### 5 comments on “Python Program to find GCD of Two Numbers”

• 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() 0
• 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)) 0
• 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) 0
• 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)) 0
• 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) 1