Python Program to find GCD of Two Numbers

Write a Python program to find GCD of two numbers using While Loop, Functions, and Recursion. To find the GCD or HCF in Python, we have to pass at least one non-zero value

The Greatest Common Divisor (GCD) is also known as Highest Common Factor (HCF), or Greatest Common Factor (GCF), or Highest Common Divisor (HCD), or Greatest Common Measure (GCM).

In Mathematics, the Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides given integer values without the remainder. For example, the GCD value of integer 8 and 12 is 4 because both 8 and 12 are divisible by 1, 2, and 4 (the remainder is 0), and the largest positive integer among them is 4.

Python Program to find GCD of Two Numbers Example 1

This python program allows the user to enter two positive integer values. Next, we are using the Python While loop to restrict the i value not to exceed the user specified values.

Within Python While loop, we used the If Statement to check whether a%i and a % i remainder equals to zero or not. If true, GCD = I otherwise, skip that value.

# Python Program to find GCD of Two Numbers

a = float(input(" Please Enter the First Value a: "))
b = float(input(" Please Enter the Second Value b: "))

i = 1
while(i <= a and i <= b):
    if(a % i == 0 and b % i == 0):
        gcd = i
    i = i + 1
    
print("\n HCF of {0} and {1} = {2}".format(a, b, gcd))

Python GCD program output

 Please Enter the First Value a: 8
 Please Enter the Second Value b: 12

 HCF of 8.0 and 12.0 = 4

Python Program to find HCF of Two Numbers Example 2

It is another approach to find the GCD of two numbers. In this python program, we are using the Temp variable to find GCD.

# Python Program to find GCD of Two Numbers

num1 = float(input(" Please Enter the First Value  Num1 : "))
num2 = float(input(" Please Enter the Second Value Num2 : "))

a = num1
b = num2

while(num2 != 0):
    temp = num2
    num2 = num1 % num2
    num1 = temp

gcd = num1   
print("\n HCF of {0} and {1} = {2}".format(a, b, gcd))

Python GCD program output

 Please Enter the First Value  Num1 : 12
 Please Enter the Second Value Num2 : 36

 HCF of 12.0 and 36.0 = 12.0

Python Program to find GCD of Two Numbers without using Temp

In this program, we are finding the GCD without using the Temp variable.

# Python Program to find GCD of Two Numbers

num1 = float(input(" Please Enter the First Value  Num1 : "))
num2 = float(input(" Please Enter the Second Value Num2 : "))

a = num1
b = num2

if(num1 == 0):
    print("\n HCF of {0} and {1} = {2}".format(a, b, b))

while(num2 != 0):
    if(num1 > num2):
        num1 = num1 - num2
    else:
        num2 = num2 - num1

gcd = num1   
print("\n HCF of {0} and {1} = {2}".format(a, b, gcd))

Python GCD program without temp value output

 Please Enter the First Value  Num1 : 75
 Please Enter the Second Value Num2 : 255

 HCF of 75.0 and 255.0 = 15.0

Python Program to find GCD of Two Numbers using Functions

This Python program is the same as above. However, we are separating the logic using Functions

# Python Program to find GCD of Two Numbers

def findgcd(num1, num2):
    if(num1 == 0):
        print("\n HCF of {0} and {1} = {2}".format(a, b, b))

    while(num2 != 0):
        if(num1 > num2):
            num1 = num1 - num2
        else:
            num2 = num2 - num1
    return num1

a = float(input(" Please Enter the First Value a: "))
b = float(input(" Please Enter the Second Value b: "))

gcd = findgcd(a, b)  
print("\n HCF of {0} and {1} = {2}".format(a, b, gcd))

Python Program to Calculate GCD of Two Numbers using Recursion

It allows user to enter two positive integer values, and calculate the Greatest Common Divisor of those two values by calling findgcd function recursively.

# Python Program to find GCD of Two Numbers

def findgcd(a, b):
    if(b == 0):
        return a;
    else:
        return findgcd(b, a % b)
    
num1 = float(input(" Please Enter the First Value  Num1 : "))
num2 = float(input(" Please Enter the Second Value Num2 : "))

gcd = findgcd(num1, num2)
print("\n GCD of {0} and {1} = {2}".format(num1, num2, gcd))

Python GCD recursion program output

 Please Enter the First Value  Num1 : 22
 Please Enter the Second Value Num2 : 88

 GCD of 22.0 and 88.0 = 22.0