Greatest Common Divisor [GCD] is a mathematical term to find the greatest common factor that can perfectly divide the two numbers. A GCD is also known as the Highest Common Factor [HCF]. For example, the HCF/ GCD of two numbers 54 and 24 is 6. Because 6 is the largest common divisor that completely divides 54 and 24.
GCD Using gcd[] Function
In python, a gcd[] is an inbuilt function offered by the math module to find the greatest common divisor of two numbers.
Syntax
Where a and b are the two integer number passes as an argument to the function gcd[].
Let's create a program to print the GCD of two number using the inbuilt function of math.gcd[] in python.
math_fun.py
Output:
In the above example, math.gcd[] function generates the GCD of two given numbers. In the gcd[] function, a and b pass as an argument that returns the greatest common divisor of two integer numbers, completely dividing the numbers.
GCD Using recursion
Recursion is a memory consuming function defined in python that calls itself via self-referential expression. It means that the function will continuously call and repeat itself until the defined condition is met to return the greatest common divisor of the number.
Pseudo Code of the Algorithm
Step 1: Take two inputs, x and y, from the user.
Step 2: Pass the input number as an argument to a recursive function.
Step 3: If the second number is equal to zero [0], it returns the first number.
Step 4: Else it recursively calls the function with the second number as an argument until it gets the remainder, which divides the second number by the first number.
Step 5: Call or assign the gcd_fun[] to a variable.
Step 6: Display the GCD of two numbers.
Step 7: Exit from the program.
Let's understand the program to find the GCD of two number using the recursion.
gcdRecur.py
Output:
GCD Using the Loop
Let's create program to find the GCD of two number in python using the loops.
gcdFile.py
Output:
As we can see in the above program, we take two values as input and pass these numbers to the GCD_Loop [] function to return a GCD.
GCD Using Euclid's algorithm or Euclidean Algorithm
Euclid's algorithm is an efficient method to find the greatest common divisor of two numbers. It is the oldest algorithm that divides the greater number into smaller ones and takes the remainder. Again, it divides the smaller number from the remainder, and this algorithm continuously divides the number until the remainder becomes 0.
For example, suppose we want to calculate the H.C.F of two numbers, 60 and 48. Then we divide the 60 by 48; it returns the remainder 12. Now we again divide the number 24 by 12, and then it returns the remainder 0. So, in this way, we get the H.C.F is 12.
Pseudo Code of the Euclid Algorithm
Step 1: There are two integer numbers, such as a and b.
Step 2: if a = 0, then the GCD[a, b] is b.
Step 3: if b = 0, the GCD[a, b] is a.
Step 4: a mod b find the
Step 5: Suppose a = b and b = R
Step 6: Repeat steps 4 and 3 until a mod b is equal or greater than 0.
Step 7: GCD = b and then print the result.
Step 8: Stop the program.
Let's find the H.C.F or GCD of two numbers using Euclid's algorithm in python.
Euclid.py
Output:
Python Basic: Exercise-31 with Solution
Write a Python program to compute the greatest common divisor [GCD] of two positive integers.
The greatest common divisor [GCD] of two nonzero integers a and b is the greatest positive integer d such that d is a divisor of both a and b; that is, there are integers e and f such that a = de and b = df, and d is the largest such integer. The GCD of a and b is generally denoted gcd[a, b].
Pictorial Presentation:
Sample Solution-1:
Python Code:
def gcd[x, y]:
gcd = 1
if x % y == 0:
return y
for k in range[int[y / 2], 0, -1]:
if x % k == 0 and y % k == 0:
gcd = k
break
return gcd
print["GCD of 12 & 17 =",gcd[12, 17]]
print["GCD of 4 & 6 =",gcd[4, 6]]
print["GCD of 336 & 360 =",gcd[336, 360]]
Sample Output:
GCD of 12 & 17 = 1 GCD of 4 & 6 = 2 GCD of 336 & 360 = 24
Flowchart:
Visualize Python code execution:
The following tool visualize what the computer is doing step-by-step as it executes the said program:
Sample Solution-2:
Python Code:
def gcd[x, y]:
z = x % y
while z:
x = y
y = z
z = x % y
return y
print["GCD of 12 & 17 =",gcd[12, 17]]
print["GCD of 4 & 6 =",gcd[4, 6]]
print["GCD of 336 & 360 =",gcd[336, 360]]
Sample Output:
GCD of 12 & 17 = 1 GCD of 4 & 6 = 2 GCD of 336 & 360 = 24
Flowchart:
Visualize Python code execution:
The following tool visualize what the computer is doing step-by-step as it executes the said program:
Sample Solution-3:
Use functools.reduce[] and math.gcd[] over the given list.
Python Code:
from functools import reduce
from math import gcd as _gcd
def gcd[nums]:
return reduce[_gcd, nums]
nums = [336, 360]
print["GCD of",','.join[str[e] for e in nums]]
print[gcd[nums]]
nums = [12, 17]
print["GCD of",','.join[str[e] for e in nums]]
print[gcd[nums]]
nums = [4, 6]
print["GCD of",','.join[str[e] for e in nums]]
print[gcd[nums]]
nums = [24, 30, 36]
print["GCD of",','.join[str[e] for e in nums]]
print[gcd[nums]]
Sample Output:
GCD of 336,360 24 GCD of 12,17 1 GCD of 4,6 2 GCD of 24,30,36 6
Flowchart:
Visualize Python code execution:
The following tool visualize what the computer is doing step-by-step as it executes the said program:
Python Code Editor:
Have another way to solve this solution? Contribute your code [and comments] through Disqus.
Previous: Write a Python program that will accept the base and height of a triangle and compute the area.
Next: Write a Python program to get the least common multiple [LCM] of two positive integers.