Python program to find the GCD or HCF

Python program to find the GCD or HCF

The largest positive integer that perfectly divides the two numbers is the HCF (Highest Common Factor) or GCD (Greatest Common Deviser). For example, the HCF or GCD of 10 and 12 is 2.

Using Loop

The following is a source code that uses a loop to find the HCF or GCD of the two numbers:

 #Program to find GCD of two numbers 
 # define a function 
 def findGCD(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)):
             GCD = i
     return GCD                              
 number1 = int(input("Enter the first number:"))
 number2 = int(input("Enter the second number:"))  
 print("The GCD of {0} and {1} is".format(number1, number2), findGCD(number1,    
 number2))

Output

Here is the result:

Explanation: In this program, we have stored two integers in a variable named number1 and number2, respectively. These numbers are passed to the function findGCD that computes the GCD of these two numbers and returns the result. In the function, we first determine the smaller of the two numbers since the GCD can only be less than or equal to the smallest number. We then use a loop to go from 1 to that number.

In each iteration, we will check if our number perfectly divides both the input numbers or not. If it divides perfectly, we store the number as GCD. After the iteration complete, the largest number that perfectly divides both the numbers will be displayed.

Using Euclidean Algorithm

This algorithm states that the GCD or H.C.F of two numbers divides their differences as well. In this algorithm, we divide the greater by smaller and take the remainder. Now, divide the smaller by this remainder. This process is repeated until the remainder becomes 0.

Example: Suppose we want to find the H.C.F of 24 and 16, then we first divide 24 by 16. The remainder will be 8. Now, we divide 16 by 8, and the remainder is 0. So, the H.C.F of these two numbers is 8.

The following is the source code to get the GCD or HCF using Euclidean Algorithm:

 #Program to find GCD of two numbers using euclidean algorithm                                        
 # define a function   
 def findGCD(a, b):  
     while (b): 
         a, b = b, a % b 
     return a                                  
 number1 = int(input("Enter the first number:")) 
 number2 = int(input("Enter the second number:")) 
 print("The CGD of {0} and {1} is".format(number1, number2), findGCD(number1,   number2)) 

Output

Here is the result:

Explanation: In this program, we have stored two integers in variables named number1 and number2, respectively. We will iterate the loop until b becomes 0. The statement a, b = b, a % b does swapping of values in Python. After each iteration, we place the value of b in a and the remainder (a % b) in b, simultaneously. When b becomes zero, we will get H.C.F. in a.

Using Recursion

The following is source code to get the HCF or GCD using recursion:

 #Program to find GCD of two numbers using recursion   
 # define a function  
 def findGCD(a, b):    
     if (b == 0): 
         return a  else:  
         return findGCD(b, a % b)                                                                                                    
 number1 = int(input("Enter the first number:"))                                                                    
 number2 = int(input("Enter the second number:"))                                                                           
 print("The GCD of {0} and {1} is".format(number1, number2), findGCD(number1, number2))  

Output

Here is the result:

Explanation: In this program, we have stored two integers in variables named number1 and number2, respectively. These numbers will be passed to the recursive function findGCD(). If the second number is equal to 0, then the GCD of two numbers will be the first number. Else the recursive function will return the GCD of two numbers.