GCD of two numbers in Python

In this article we will look at different solutions for finding the GCD (Greatest Common Divisor) or HCF (Highest Common Factor) for two numbers in Python programming language. Different solutions are provided from solution with high time complexity to solution with less time complexity for calculating GCD of two numbers in Python.

Solution 1

#A very basic Python program to find the GCD of two numbers
#Author: P.S.Suryateja
#Website: startertutorials.com

lsta = []
lstb = []
lstcf = []

#Function to find factors of a given number
def findfactors(n, lst):
	for i in range(1, n+1):
		if n % i == 0:
			lst.append(i)

#Function to find the common factors between two numbers
def commonfact():
	for i in lsta:
		if i in lstb:
			lstcf.append(i)

def gcd(m, n):
	findfactors(m, lsta)
	findfactors(n, lstb)
	commonfact()
	print(lstcf[-1]) #Prints the last element in the list which is the GCD
	
gcd(16, 12)

Solution 2

#An improved Python program to find the GCD of two numbers
#Author: P.S.Suryateja
#Website: startertutorials.com
#Instead scanning two times up to maximum of m and n we only scan up to minimum of m and n
#GCD cannot be greater than minimum of m and n
#One list is enough to maintain the common factors

lstcf = []

#Function to find factors of a given number
def findfactors(m, n):
	for i in range(1, min(m,n)+1):
		if m%i==0 and n%i==0:
			lstcf.append(i)

def gcd(m, n):
	findfactors(m,n)
	print(lstcf[-1]) #Prints the last element in the list which is the GCD
	
gcd(16, 12)

Solution 3

#An improved Python program to find the GCD of two numbers
#Author: P.S.Suryateja
#Website: startertutorials.com
#This program doesn't use lists at all to store the common factors

def gcd(m, n):
	cf = 1
	for i in range(1, min(m,n)+1):
		if m%i==0 and n%i==0:
			cf = i
	return cf
	
print(gcd(16, 12))

Solution 4

#An improved Python program to find the GCD of two numbers
#Author: P.S.Suryateja
#Website: startertutorials.com
#We scan from the back in the range instead of starting from 1

def gcd(m, n):
	for i in range(min(m,n),1,-1):
		if m%i==0 and n%i==0:
			return i
	return 1
	
print(gcd(16, 12))

Solution 5 (Euclid’s algorithm) – Recursive Solution

#Euclid's algorithm for finding the GCD of two numbers in Python
#Recursive solution
#Author: P.S.Suryateja
#Website: startertutorials.com

def gcd(m, n):
	if m < n:
		(m,n) = (n,m)
	if m%n == 0:
		return n;
	else:
		return gcd(n, m%n)
	
print(gcd(16, 12))

Solution 6 (Euclid’s algorithm) – Iterative Solution

#Euclid's algorithm for finding the GCD of two numbers in Python
#Iterative solution
#Author: P.S.Suryateja
#Website: startertutorials.com

def gcd(m, n):
	if m < n:
		(m,n) = (n,m)
	while m%n != 0:
		(m,n) = (n, m%n)
	return n
	
print(gcd(16, 12))

Output

4

Suryateja Pericherla

Suryateja Pericherla, at present is a Research Scholar (full-time Ph.D.) in the Dept. of Computer Science & Systems Engineering at Andhra University, Visakhapatnam. Previously worked as an Associate Professor in the Dept. of CSE at Vishnu Institute of Technology, India.

He has 11+ years of teaching experience and is an individual researcher whose research interests are Cloud Computing, Internet of Things, Computer Security, Network Security and Blockchain.

He is a member of professional societies like IEEE, ACM, CSI and ISCA. He published several research papers which are indexed by SCIE, WoS, Scopus, Springer and others.