GCD of Two Numbers in Python
FREE
Introduction
GCD stands for Greatest Common Divisor. It is used to calculate the HCF(Highest Common Factor), i.e., GCD(greatest common divisor) for two numbers is a number that can perfectly divide the two numbers.
Introduction to GCD of two numbers in Python
GCD(Greatest Common Divisor) is a mathematical term that explains calculating the greatest common factor of two numbers. The GCD of two or more integers that are not all zero is the largest positive integer dividing both integers.
GCD is also known as HCF(Highest Common factor).
In this example, we will see how to calculate the GCD of two numbers.
Example: There are two numbers, 4 and 10. What is the GCD/HCF of 4 and 10?
As we discuss the definition of GCD, it tells us the highest common factor that divides two numbers. In the case of 4 and 10, the highest common factor is 2.
Calculating GCD of Two Numbers in Python using gcd() function
There are various methods to calculate the GCD of two numbers. One of the methods is using the gcd() function that is available in the math module in python.
Note: For calculating the gcd of two numbers using gcd() function. It is mandatory to import the math module. If the math module is not imported it will throw ImportError.
Syntax The syntax of gcd() function:
Parameters
- x 'x' is a non-negative integer whose GCD/HCF we have to compute.
- y 'y' is also a non-negative integer whose GCD/HCF we have to compute.
Return Type math.gcd() function will return a non-negative integer, the highest common factor i.e., the GCD of x,y.
Note: If we entered x and y both as 0. The function will return 0, and if we are using any other data type instead of int it will throw TypeError.
Example
Input:
Output:
GCD of Two Numbers in Python Using Recursion
We will now use the Recursion technique to calculate the GCD of two numbers.
Input:
Output:
GCD of Two Numbers in Python Using Euclidean Algorithm
Euclidean Algorithm is the most efficient algorithm to calculate the GCD of two numbers.
So, the Euclidean algorithm states that we first store the greater number and the smaller number, then we divide the greater number by the smaller number and store the remainder.
The stored remainder should be divided by a smaller number, and keep repeating this process until the remainder is equal to 0.
Example: We have two numbers, 24 and 54. Now according to Euclidean Algorithm, we divide 54%24 = 6 and store 6. Now divide 24%6 = 0. Now our remainder is 0. So, our result is 6 i.e., the GCD of 24 and 54 is 6.
Using LOOPS
Input:
Output:
USING RECURSION
Input:
Output:
GCD of Two Numbers in Python Using Loops
Input:
Output:
Explanation: n stores the minimum value of x and y value because the HCF(highest common factor) of two numbers always lies between the 1 and minimum of two numbers. So, n can store the minimum value of two numbers.
The for loop will run for n+1 times because n+1 is exclusive in the for loop. For every step, check that both the numbers are divisible by the current value. If both values are divisible by the current value of for loop, then hcf will be the current value of for loop. After the successful execution of for loop, our program will result in the HCF(highest common factor) of x and y.
Click here to know more about min() in python.
Conclusion
- GCD is a mathematical tool that tells us about the highest common factor of two numbers.
- We can use the built-in gcd() function, which is available in the math module to find gcd of 2 numbers.
- We can find gcd using one of the popular algorithms, i.e., Euclidean Algorithm to calculate the GCD.