Greatest common divisor in Python
Problem
Given two integers A less than B. Write Python code to find the greatest common divisor between A and B commonly known as GCD.
Definition
GCD(A, B) is the largest positive integer that divides A and B without a remainder. We can loop starting at 2 ending at A and whenever we find a divisor for both A and B we update our result. At the end of the loop we will have GCD already computed.
Solution
Here is a sample Python code to do that
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Example numbers A = 51 B = 85 # By default GCD = 1 gcd = 1 # Check all numbers from 2 to A (smaller one) for i in range (2, A+1): # If the current number divides both of them # update GCD if A%i == 0 and B%i == 0: gcd = i # At the end we will have GCD computed print "GCD = {}".format(gcd) |
Euclidean algorithm
We can use the Euclidean algorithm to solve this problem efficiently. The Euclidean algorithm is based on the fact that the GCD of two numbers does not change if the smaller number is subtracted from the larger number. Here is an example:
|
1 |
GCD(51, 85) = GCD(34, 51) = GCD(17, 34) = GCD(17, 17) = GCD(0, 17) = 17 |
Code
Here is an iterative implementation in Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def GCD(A, B): if A == 0: return B while B != 0: if A > B: A = A - B else: B = B - A return A A = 51 B = 85 print "GCD of {} and {} is {}".format(A, B, GCD(A, B)) |
Here is the recursive Python version of the Euclidean algorithm
|
1 2 3 4 5 6 7 8 9 10 11 |
int GCD(int A, int B) def GCD(A, B): if B == 0: return A else: return GCD(B, A%B) A = 51 B = 85 print "GCD of {} and {} is {}".format(A, B, GCD(A, B)) |
If you have questions or comments, please use the comments section below. Thanks for reading.
About Author
Mohammed Abualrob
Software Engineer @ Cisco