## đź“śIntroduction

The mathematical term GCD (Greatest Common Divisor) describes finding the biggest common factor between two values. The greatest positive integer that divides two or more numbers that are not all zeros is called the GCD. H.C.F. is another name for GCD (Highest Common factor).

Example: There are two numbers, 5 and 10. What is the GCD/HCF of 5 and 10?

As we discuss the definition of GCD, it tells us the highest common factor or greatest common divisor that divides two numbers. In the case of 5 and 10, the highest common factor is 5.

We will be discussing the various methods to find the GCD of two numbers in python by using:

đź’ˇgcd() function

đź’ˇrecursion

đź’ˇloops

đź’ˇEuclidean Algorithm

Must Recommended Topic, __Floor Division in Python____, ____Swapcase in Python__

## đź¤”Find GCD of Two Numbers in Python Using gcd() Function.

We can find GCD of two numbers in Python in several ways. Utilizing the math module's gcd() function is one of the techniques.

While using the gcd() function to find the gcd of two numbers in python, the math module must be imported. The math module will raise an import error if it is not imported.

### đź“šSyntax

`math.gcd(x, y)`

#### Parameters

**x:** Non-negative integer passed as a first argument.

**y:** Non-negative integer passed as a second argument.

#### Return Type

The math will return the GCD of x and y, the highest common factor.

### đź§‘â€Ťđź’»Code

```
#The math module contains the gcd function
import math
#Calculating the gcd of 2 numbers.
x = 10
y = 5
hcf = math.gcd(x,y)
print(f"The computed GCD of {x} and {y} is {hcf}.")
```

**Output**

## đź¤”Find GCD Of Two Numbers In Python Using Recursion

__Recursion__ is a memory-intensive __Python____ __function that uses self-referential expression to call itself. To return the number's greatest common divisor, the function will keep calling and repeating itself until the predetermined condition is satisfied.

### đź“šAlgorithm

**Step 1:** Take two user inputs, x and y.

**Step 2:** Pass the inputs as arguments to the recursive function.

**Step 3:** If the second number equals zero, it returns the first number.

**Step 4:** Else, recursively call the function with the second parameter as an argument until it gets the remainder, which divides the second parameter by the first.

### đź§‘â€Ťđź’»Code

```
# The math module contains the gcd function
import math
#Calculating the gcd of 2 numbers.
def gcd(x,y):
if y == 0:
return x
else:
return gcd(y,x%y)
x=10
y=18
print(f"The computed GCD of {x} and {y} is {gcd(100,3)}."
```

**Output**

## đź¤”Find GCD Of Two Numbers In Python Using Loops

### đź§‘â€Ťđź’»Code

```
# The math module contains the gcd function
import math
#Calculating the gcd of 2 numbers.
x = 86
y = 44
n = min(x,y)
gcd = 0
for i in range(1,n+1):
if x%i == 0 and y%i == 0:
gcd = i
print(f"The computed GCD of {x} and {y} is {gcd}.")
```

**Output**

Because the H.C.F. (highest common factor) of two numbers always lies between 1 and the minimum, the variable n saves the minimum value of x and y. Due to the for loop's exclusive use of n+1, it will execute for n+1 times. Verify that both values may be divided by the current value at each step. If the current value of the for loop divides both values, the current value of the for loop will be hcf. The H.C.F. (highest common factor) of x and y will be returned after completing the loop successfully.

You can try it on online python compiler.