Python Program to Find GCD or HCF of two numbers

The full form of GCD is " Greatest Common Divisor". Which means the greatest common factor of the two numbers. It is also known by the name HCF(Highest common factor). I will be using both the words so don't confuse yourself.

I have used for loop, if-else statement, min() function and break statement.

We have checked both numbers by dividing them every number less than the minimum of both the numbers. And if that number divides both the numbers without leaving any remainder than that number becomes the HCF of the given numbers. And remember that I am running the loop in reverse order.

Code:

# taking first number
num1 = int(input("Enter first number: "))         
# taking second number      
num2 = int(input("Enter second number: "))              

gcd = 1

# finding GCD
for i in range(min(num1,num2),0,-1):                    
    if (num1%i) == 0 and (num2%i) == 0:
        gcd = i
        break
    
# printing GCD
print("The GCD of the two numbers is ", gcd)

Output:-

We can use Euclid's Algorithm to solve this problem much faster.

Finding GCD or HCF of two numbers using Euclid's algorithm in python

In this method, we are going to use Euclid's algorithm which is much faster. I have used while loop, if-else statement, and swapping technique.

Code:

# taking first number
num1 = int(input("Enter first number: "))
# taking second number           
num2 = int(input("Enter second number: "))          

# checking if num2 is greater than num1 then swap these numbers
if num2 > num1:                                     
    (num1,num2) = (num2,num1)
# repeat these steps till num2 divides num1 with remainder zero
while num1%num2 != 0:                              
    # swap num1 to num2 and num2 with remainder
    (num1,num2) = (num2,num1%num2)                  

# printing GCD
print("The GCD of the numbers is ",num2)

Output:-

We can use Euclid's algorithm with recursion.

Finding GCD or HCF of two numbers by Euclid's algorithm using recursion in python

Here we have made a recursive function gcd().

Code:

# defining gcd function
def gcd(num1,num2):
    if num1%num2 == 0:
        # Base case
        return num2
    else:
        # Iterative case
        return gcd(num2,num1%num2)

# taking first number
num1 = int(input("Enter first number: "))
# taking second number           
num2 = int(input("Enter second number: "))          

# checking if num2 is greater than num1 then swap these numbers
if num2 > num1:                                     
    (num1,num2) = (num2,num1)

# printing GCD
print("The GCD of the numbers is",gcd(num1,num2))

Output:-

In this program, we used many things which I used to make previous programs and also learnt about many other things about python.

Now you can try some other programs. And If you find any problem then you can always contact me or comment below.