Online Ethical Hacking Course

Apply Now

Examples

GCD of Two Numbers in Python (Program to Find HCF or GCD)

Looking to calculate GCD of two numbers in Python using different methods and programs? We have covered it in simple terms here. In this step-by-step guide, you will find the GCD program in Python with proper code, output, explanation, and option to practice with an online Python compiler.

The GCD (Greatest Common Divisor) or HCF (Highest Common Factor) is a fundamental mathematical concept that represents the largest positive integer dividing two or more numbers without leaving a remainder. 

It plays a crucial role in simplifying fractions, reducing fractions to their lowest terms, and solving linear Diophantine equations. By mastering HCF in Python, you can open doors to numerous new possibilities in fields such as cryptography, number theory, and algorithm design.

With our tutorial as your guiding light, you will hold mastery at Python program to find GCD of two numbers. From reducing fractions to optimizing your algorithms, you'll be empowered to tackle complex problems with confidence.

If you are a beginner, it is recommended to learn the concepts with our Python Tutorial or an expert-led Python Course. 

GCD Program in Python

Below is a simple program to find the greatest common divisor in Python using the Euclidean algorithm:

Code

# Find GCD of HCF of Two Numbers in Python

def find_gcd(num1, num2):
    while num2 != 0:
        num1, num2 = num2, num1 % num2
    return num1

# Test the function
number1 = int(input("Enter the first number: "))
number2 = int(input("Enter the second number: "))
result = find_gcd(number1, number2)
print("The GCD of", number1, "and", number2, "is", result)

Output

Enter the first number: 270
Enter the second number: 192
The GCD of 270 and 192 is 6

Explanation

  • In this code, the find_gcd function takes two numbers as input (num1 and num2). It uses the Euclidean algorithm to iteratively find the GCD. 

  • The algorithm repeatedly divides the larger number by the smaller number and assigns the remainder to the larger number. This process continues until the remainder becomes zero. The final non-zero remainder is the GCD of the two numbers.

  • The function returns the GCD, which is then printed to the console. The user is prompted to enter two numbers, and the function is called with these numbers as arguments.

Python Course

GCD of Two Numbers in Python Using for loop

Here's how to find GCD of two numbers in Python using a for loop:

Code

def find_gcd(num1, num2):
    gcd = 1
    # Find the smaller of the two numbers
    smaller = min(num1, num2)
    
    # Start the loop from 2 up to the smaller number
    for i in range(2, smaller + 1):
        # Check if both numbers are divisible by the current value of i
        if num1 % i == 0 and num2 % i == 0:
            gcd = i
    
    return gcd

# Test the function
number1 = int(input("Enter the first number: "))
number2 = int(input("Enter the second number: "))
result = find_gcd(number1, number2)
print("The GCD of", number1, "and", number2, "is", result)

Output

Enter the first number: 54
Enter the second number: 42
The GCD of 54 and 42 is 6

Explanation

  • Here, the find_gcd function takes two numbers as input (num1 and num2). It initializes the GCD to 1 and finds the smaller of the two numbers. 

  • The for loop iterates from 2 up to the value of the smaller number. Inside the loop, it checks if both num1 and num2 are divisible by the current value of i. If they are, it updates the gcd variable with the value of i.

  • Finally, the function returns the GCD, which is then printed to the console. The user is prompted to enter two numbers, and the function is called with these numbers as arguments.

Note:

This program uses a for loop, but it is not the most efficient algorithm for finding the GCD. The Euclidean algorithm is a more efficient approach, as shown in the previous example.

GCD of Two Numbers in Python Using Recursion

Here's an example of the highest common factor program in Python using recursion:

Code

def find_gcd(num1, num2):
    if num2 == 0:
        return num1
    else:
        return find_gcd(num2, num1 % num2)

# Test the function
number1 = int(input("Enter the first number: "))
number2 = int(input("Enter the second number: "))
result = find_gcd(number1, number2)
print("The GCD of", number1, "and", number2, "is", result)

Output

Enter the first number: 273
Enter the second number: 80
The GCD of 273 and 80 is 1

Explanation

  • In this code, the find_gcd function takes two numbers as input (num1 and num2). It uses recursion to find the GCD. The base case is when num2 becomes zero, in which case it returns num1 as the GCD. Otherwise, it calls itself with the arguments num2 and num1 % num2, which represents the remainder of dividing num1 by num2.

  • The function continues to call itself recursively until it reaches the base case, and then it starts unwinding the recursion, returning the GCD back to the initial call.

  • Finally, the GCD is printed to the console. The user is prompted to enter two numbers, and the function is called with these numbers as arguments.

Note:

Recursion can be an elegant way to solve problems, but it's important to note that it may not be the most efficient approach for very large numbers due to the additional overhead of function calls.

GCD of Two Numbers in Python Using while loop

Using a while loop is another way to find the GCD, and it provides an alternative approach to the recursion and for loop methods.

Code

def find_gcd(num1, num2):
    while num2 != 0:
        remainder = num1 % num2
        num1 = num2
        num2 = remainder
    return num1

# Test the function
number1 = int(input("Enter the first number: "))
number2 = int(input("Enter the second number: "))
result = find_gcd(number1, number2)
print("The GCD of", number1, "and", number2, "is", result)

Output

Enter the first number: 24
Enter the second number: 36
The GCD of 24 and 36 is 12

Explanation

  • Here, the find_gcd function takes two numbers as input (num1 and num2). It uses a while loop to repeatedly calculate the remainder of dividing num1 by num2 and update the values of num1 and num2 accordingly. This process continues until num2 becomes zero.

  • The GCD is the final non-zero remainder, which is stored in num1. The function returns num1 as the GCD.

  • Finally, the GCD is printed to the console. The user is prompted to enter two numbers, and the function is called with these numbers as arguments.

Practice More Python Programs:

Useful Python Resources:

Program to Find HCF or GCD of Two Numbers in Python: Video