Python GCD function

In this post, we will see how to find Highest common factor(H.C.F) or greatest common divisor(G.C.D)
Highest common factor or greatest common division is the highest integer which completely divides the number.
For example: HCF of 12 and 18 is 6.
There are many ways to find HCF and we will see two ways.


Simple solution

  • Find smaller number among two numbers
  • Iterate upto small number using range function and check remainder
  • If current num is divisible by both numbers, update the HCF
# HCF def findHCF(a,b): # choose the smaller number if a > b: smaller = b else: smaller = a for i in range(1, smaller+1): if((a % i == 0) and (b % i == 0)): hcf = i return hcf num1 = 12 num2 = 18 # If you want to take input from user, uncomment below lines # num1 = int(input("Enter first number: ")) # num2 = int(input("Enter second number: ")) print("The H.C.F. of", num1,"and", num2,"is", findHCF(num1, num2))

Using Euclidean algorithm

Euclidean algo for calculating GCD is:

Lets say , there are two numbers , a and b so
GCD of two numbers = GCD (b,a%b) and GCD(a,0)=a

# HCF # Using Eucid algorithm for calculating gcd def gcd(a,b): if(b==0): return a else: return gcd(b,a%b) num1 = 12 num2 = 18 # If you want to take input from user, uncomment below lines # num1 = int(input("Enter first number: ")) # num2 = int(input("Enter second number: ")) print("The H.C.F. of", num1,"and", num2,"is", gcd(num1, num2))

You can use iterative method for the same too.

# HCF # Using Eucid algorithm for calculating gcd def gcd(a,b): while(b!=0): a,b=b,a%b return a num1 = 12 num2 = 18 # If you want to take input from user, uncomment below lines # num1 = int(input("Enter first number: ")) # num2 = int(input("Enter second number: ")) print("The H.C.F. of", num1,"and", num2,"is", gcd(num1, num2))

That’s all about finding HCF or GCD of two numbers.

Leave a Reply

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