In this post, you will learn how to find the greatest common divisor (G.C.D) or highest common factor (H.C.F) of numbers using different methods in Python programming language.
Greatest common divisor (G.C.D) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers a, b, the greatest common divisor of a and b is denoted gcd(a,b). These are different ways to find the GCD or HCF using Python.
GCD in Python using math.gcd() Method
In Python, the math module contains various mathematical functions, which can be performed effortlessly utilizing the module. The math.gcd() method computes the greatest common divisor of two numbers.
Syntax of math.gcd()
Here, x and y are non-negative integers for computing GCD. It returns a positive integer value representing the greatest common divisor (GCD) for two integers.
Python gcd Example
import math # Greatest common divisor of the two integers print("GCD of (5, 2) = ",math.gcd(5, 2)) print("GCD of (4, 10) = ",math.gcd(4, 10)) print("GCD of (10, 0) = ",math.gcd(10, 0)) print("GCD of (-9, -16) = ",math.gcd(-9, -16)) print("GCD of (4, 14) = ",math.gcd(4, 14)) print("GCD of (6, 3) moduletable">
GCD in Python using for loop
Here, we define a function to compute the H.C.F of two numbers and return it. In each iteration, we check if our number perfectly divides both the user input numbers. If this is true, we store the number as H.C.F. At the completion of the loop, we conclude with the largest number that perfectly divides both the numbers.
# Python program to find GCD of two numbers # define a function def get_gcd(a, b): # pick the smaller number if a > b: smaller = int(b) else: smaller = int(a) for i in range(1, smaller+1): if((a % i == 0) and (b % i == 0)): gcd = i return gcd x = input("Enter the first number: ") y = input("Enter the second number: ") print("The G.C.D. is ", get_gcd(int(x), int(y)))
Enter the first number: 39 Enter the second number: 2 The G.C.D. is 1 Enter the first number: 48 Enter the second number: 34 The G.C.D. is 2
GCD in Python using while loop
In the given Python program, we have used the while loop to compute the GCD of two numbers.
x = int(input('Please input the first integer:')) y = int(input('Please input the second integer:')) while y != 0: gcd = y y = x % y x = gcd print("The G.C.D. is ",gcd)
Please input the first integer:6 Please input the second integer:10 The G.C.D. is 2
GCD in Python using Recursion
Recursion function is a function which is calling itself. The following code finds the greatest common divisor of user inputs using the recursion function. A recursion function continues until some condition is met to prevent it. That's why we use the if statement to break the infinite recursion.
def compute_gcd(a, b): if(b == 0): return a else: return compute_gcd(b, a % b) x = input("Enter the first number: ") y = input("Enter the second number: ") print("The G.C.D. is ", compute_gcd(int(x), int(y)))
Output of the above code-
GCD in Python using Euclidean algorithm
The Euclidean algorithm is an efficient way to find the greatest common divisor of two numbers, the largest number that divides them both without a remainder.
# Function to find GCD the Using Euclidian algorithm def compute_gcd(a, b): while(b): a, b = b, a % b return a x = input("Enter the first number: ") y = input("Enter the second number: ") print("The G.C.D. is ", compute_gcd(int(x), int(y)))
Enter the first number: 78 Enter the second number: 40 The G.C.D. is 2 Enter the first number: 30 Enter the second number: 15 The G.C.D. is 15
A factor is a number that can go into another number without a remainder. A dividend divides a divisor to give the quotient. If the dividend and the divisor is a whole number and if the quotient has a remainder of zero (no remainder), then the divisor is called a factor of the dividend. Greatest Common Divisor is abbreviated, G.C.D or simply gcd. Another name for Greatest Common Divisor is Highest Common Factor, abbreviated H.C.F.
Finding G.C.F by Definition
The problem is to find the highest common factor also called the greatest common divisor for the numbers 108 and 240.
All the factors greater than 1 are placed in the following table:
The first row has the factors of 108 in ascending order. The second row has the factors of 240 in ascending order.
Common factors (divisors) for 108 and 240 are: 2, 3, 4, 6, and 12.
By inspection, the greatest factor (divisor) that is common to the numbers 108 and 240 is 12. That is, gcd or H.C.F for 108 and 240 is 12.
Writing a program that will find the gcd, as explained above, will take too long. Two shorter methods to find the gcd are: GCD by Subtraction and GCD by Division.
GCD by Subtraction
By inspection from the above table, gcd for 108 and 240 is 12. This means that if 12 is added repeatedly, the result will become 108 which is the smaller of both numbers. If the addition of 12 continues, then the result will become 240 which is the bigger of both numbers. That is:
If the gcd can be added repeatedly to give any of the numbers (108 and 240) from which the gcd is required, then it might be possible to do some kind of subtraction repeatedly, beginning with the given numbers to have the gcd. In fact, it is possible to do a particular kind of subtraction repeatedly and get the gcd. This begins with the difference of the given numbers.
Problem: Find the greatest common divisor (highest common factor) for 108 and 240 by subtraction.
Between 108 and 240, 240 is the bigger number. After the difference of these given numbers, the difference of the resulting difference (132 for the first step) and the subtrahend (108 for the first step) are obtained repeatedly until the final difference is zero. In the steps, the smaller number is subtracted from the bigger number. At the last step, the minuend and the subtrahend are the same. This same value is the greatest common divisor.
Let the numbers whose gcd is needed be ‘a’ and ‘b’. If these numbers have no gcd greater than 1, it means that their greatest common divisor is 1. In programming, the time complexity to find the gcd by subtraction is O(a+b). If ‘a’ is 1 and b is 6, then the steps without programming, will be:
The gcd here is 1. There are six steps here and not seven steps by (a + b). However, in programming, the maximum possible number of code operations is what is taken as the time complexity.
Coding GCD by Subtraction
The function for the greatest common divisor by subtraction, in Python, is:
def gcds ( a, b ) : if a == b: return a if a > b: return gcds ( a - b, b ) else: return gcds ( a, b – a )
The first statement takes care of the last math step. The next compound statement (if/else) does the subtraction between the minuend and the difference, depending on which one is bigger.
In-depth Look at the GCD Math Subtractions
132 = 12 x 11 ( 132 has 12 as a factor )
24 = 12 x 2 ( 24 has 12 as a factor )
84 = 12 x 7 ( 84 has 12 as a factor )
60 = 12 x 5 ( 60 has 12 as a factor )
36 = 12 x 3 ( 36 has 12 as a factor )
12 = 12 x 1 ( 12 has a factor or 12 – itself )
12 = 12 x 1 ( 12 has a factor or 12 – itself )
The last step has a difference of 0. It marks the end of the subtraction steps and gives the gcd as the subtrahend or minuend.
Now, if the gcd can be multiplied by a whole number (positive integer) to give any of the numbers (108 or 240) from which the gcd is required, then it might be possible to do some kind of division repeatedly, beginning with the given numbers to have the gcd. In fact, it is possible to do a particular kind of division repeatedly and get the gcd. This division is a special repeating modulus division. It begins with the modulus division of the given numbers.
In Modulus division, when the dividend is divided by the divisor, the remainder for the quotient is the answer.
Problem: Find the greatest common divisor (highest common factor) for 108 and 240 by modulus division:
At the last line, where the remainder is zero, the divisor is the greatest common divisor (highest common factor).
This problem is to find the gcd between 108 and 240 by division. The solution here took 3 steps. The previous problem was similar but it was to look for the same gcd by subtraction; and it had 8 steps. While the time complexity for the subtraction method is O(a+b), the time complexity for the division method is O(log(a + b)).
In modulus division, it does not matter whether ‘a’ is bigger than b or b is bigger than ‘a’; the remainder is the same positive integer.
Find mathematically, the greatest common divisor by division, for the numbers, 5 and 2.
The gcd is 1. This needed two mathematical steps.
Coding GCD by Division
The word, “division” here refers to modulus division. The function is:
The if-part of the if/else-construct takes care of the last mathematical statement, for the steps of modulus division. The else part takes care of the actual modulo division (resulting in the remainder). In modulus division, it does not matter whether ‘a’ is bigger than b or b is bigger than ‘a’; the remainder is the same positive integer.
To call and print out a gcd, the following code can be used:
In-depth Look at the GCD Math Divisions
240 % 108 = 24 ( The gcd between 240 and 108 is 12 )
24 = 12 x 2 ( 24 has 12 as a factor )
108 % 24 = 12 ( The gcd between 108 and 24 is 12 )
12 = 12 x 1 ( 12 has 12 as a factor, itself )
24 % 12 = 0 ( The gcd between 24 and 12 is 12 )
It has been demonstrated here, that:
where ‘a’ and b are two different whole numbers and ‘r’ is the remainder of division between a and b. b may be bigger than ‘a’ or ‘a’ may be bigger than b. Thus, if the remainder of a division is not zero, then the greatest common divisor between the two given numbers is the same as the greatest common divisor between the divisor and the remainder. This runs down in different steps until the remainder is zero, even if the gcd is 1.
The last step has a remainder of 0. It marks the end of the modulus division steps and the gcd is the divisor.
Conclusion
The Greatest Common Divisor can be determined by repeated subtractions or repeated modulo divisions.
If it is by subtraction, then after the subtraction of the given numbers, the rest of the subtractions are between the difference and the minuend, depending on which one is bigger. When the difference is zero, the subtrahend is equal to the minuend, and either is the gcd.
If it is by division, then the repeated divisions are modulus divisions. In this situation, after the modulus division of the given numbers, the rest of the modulus divisions are between the divisor and the remainder, depending on which one is bigger. When the remainder is zero, the divisor is the gcd. Strictly speaking, in modulus division, it does not matter whether ‘a’ is bigger than b or b is bigger than ‘a’; the remainder is the same positive integer.
About the author
Chrysanthus Forcha
Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.
