interview questions

Find GCD of two numbers

Last Updated on

Hello,

In this article, we will see how to find GCD of 2 numbers in Python language. This article is part of our tech interview preparation series.

What is GCD?

GCD(Greatest common divisor) or HCF(Highest common factor) is common factor between 2 or more numbers which is divisible by both.

GCD of 4 and 6 is 2. Here both 4 and 6 have common factor 2.

GCD of 10,25,40 is 5

How to calculate GCD between 2 numbers?

To find our GCD between 2 numbers, you need to take factors of both numbers, and see the common factors. GCD is product of common factors.

For example : To calculate GCD of 4 and 6

Factor of 4 = 1,2,4

Factor of 6 = 1,2,3,6

Common factors= 1,2

GCD=2

How to find GCD between 2 number in Python

def getFactor(number):
	factors = []
	i=1
	while(i<number+1):
		if(number%i==0):
			factors.append(i)
		i+=1
	return factors

def getCommon(a,b): 
    c = [value for value in a if value in b] 
    c.sort()
    c.reverse()
    return c[0]


def getGCD(num1,num2):
	if(num1==num2):
		return num1

	if(num1%num2==0):
		return num2

	if(num2%num1==0):
		return num1

	factor_num1 = getFactor(num1)
	factor_num2 = getFactor(num2)
	return getCommon(factor_num1,factor_num2)

print(getGCD(320,400))

End note

In the article, you have seen how to find GCD between 2 or more number in Python.

If in case you have doubt regarding implementation, please feel free to share us your concerns in discussion thread below, or mail us to info@xamnation.com

This article is for technical interview preparation. Find more useful programming exercises in link below.

  • How to check whether string is palindrome or not
  • How to find prime numbers between a given range
  • How to check whether number is Armstrong number

Xamnation is helping students in interview preparation and learning programming language. We are offering live classes, study material and interview preparation course. Please find below useful course.

  • Aptitude preparation course for job interviews
  • Puzzles course for job interviews
  • Python course for job interviews
  • Amazon job preparation course
  • TCS job preparation course

Leave a Comment

Your email address will not be published. Required fields are marked *