# Python Program to find GCD of Two Numbers

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

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

In Mathematics, the Greatest Common Divisor of two or more integers is the largest positive integer that divides given integer values without the remainder. For example, the GCD value of integers 8 and 12 is 4 because 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 the GCD of Two Numbers using a while loop

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

Within the While loop, we used the If Statement to check whether a%i and a % i remainder equal to zero or not. If true, the Highest Common Factor = I; otherwise, skip that value.

```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):
val = i
i = i + 1

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

It is another approach to finding the HCF or GCD, the Greatest Common Factor of two numbers in Python using a while loop. In this program, we are using the Temp variable to find GCD.

```num1 = float(input(" First : "))
num2 = float(input(" Second : "))

a = num1
b = num2

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

hcf = num1
print("\n HCF of {0} and {1} = {2}".format(a, b, hcf))```
`````` First : 12
Second : 36

HCF of 12.0 and 36.0 = 12.0``````

## Python Program for HCF of Two Numbers using gcd function

There is a built-in math function called the gcd() function that accepts two arguments and returns their HCF. This function accepts only integer values.

```import math

a = int(input("First : "))
b = int(input("Second : "))

hcf = math.gcd(a, b)

print(hcf)```
``````First : 30
Second : 18
6``````

## Python Program to find the GCD of Two Numbers without using Temp

In this program, we find the GCD of two numbers without using the Temp variable. It uses the arithmetic minus operator to subtract one variable from another and finds the result.

```num1 = float(input(" First : "))
num2 = float(input(" Second : "))

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

hcf = num1
print(hcf)```
`````` First : 75
Second : 255

HCF of 75.0 and 255.0 = 15.0``````

## Python Program to find the GCD of Two Numbers using for loop

This program uses the for loop to iterate from 1 to the minimum number between two. Next, we find the divisor of the num1 and num2 variables and store the highest value in the result variable.

```num1 = int(input("First  : "))
num2 = int(input("Second : "))

for i in range(1, min(num1, num2) + 1):
if num1 % i == 0 and num2 % i == 0:
result = i

print(result)```

## Python Program to find the GCD of Two Numbers using Functions

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

```def findresult(val1, val2):
if(val1 == 0):
print("\n HCF of {0} and {1} = {2}".format(a, b, b))

while(val2 != 0):
if(val1 > val2):
val1 = val1 - val2
else:
val2 = val2 - val1
return val1

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

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

We can try the below code to find the Greatest Common Divisor or Highest Common Factor. Instead of writing the If else conditions, you. can use. the assignment operator (=) to assign values to multiple variables.

```def calgcd(a, b):
while (b):
a, b = b, a % b
return a

x = float(input("First : "))
y = float(input("Second : "))

hcf = calgcd(x, y)

print("Result =", hcf)```
``````First : 98
Second : 77
Result = 7.0``````

## Python Program to find the GCD of Two Numbers using Recursion

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

```def findGreatestCD(a, b):
if(b == 0):
return a;
else:
return findGreatestCD(b, a % b)

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

Val = findGreatestCD(num1, num2)
print("\n The Result of {0} and {1} = {2}".format(num1, num2, Val))```

### How to find HCD or HCF using Ternary Operator?

This example helps you write the complete code in a single lie.

```def findHCF(a, b):
return a if b == 0 else findHCF(b, a % b)

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

print(findHCF(num1, num2))```
``````Enter the First Value  : 76
Enter the Second Value : 128
4.0``````

### GCD of Two Numbers using Reducing Algorithm

This example uses the reducing algorithm approach with the help of the if statement.

```def findHCF(a, b):
if a == 0:
return b
if b == 0:
return a
if a == b:
return a
if a > b:
return findHCF(a - b, b)
return findHCF(a, b - a)

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

print(findHCF(num1, num2))```
``````Enter the First Value  : 22
Enter the Second Value : 44
22.0``````