Code for Greatest Common Divisor in Python
PythonPython Problem Overview
The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder.
One way to find the GCD of two numbers is Euclid’s algorithm, which is based on the observation that if r is the remainder when a is divided by b, then gcd(a, b) = gcd(b, r). As a base case, we can use gcd(a, 0) = a.
Write a function called gcd that takes parameters a and b and returns their greatest common divisor.
Python Solutions
Solution 1 - Python
It's in the standard library.
>>> from fractions import gcd
>>> gcd(20,8)
4
Source code from the inspect module in Python 2.7:
>>> print inspect.getsource(gcd)
def gcd(a, b):
"""Calculate the Greatest Common Divisor of a and b.
Unless b==0, the result will have the same sign as b (so that when
b is divided by it, the result comes out positive).
"""
while b:
a, b = b, a%b
return a
As of Python 3.5, gcd is in the math module; the one in fractions is deprecated. Moreover, inspect.getsource no longer returns explanatory source code for either method.
Solution 2 - Python
The algorithms with m-n can runs awfully long.
This one performs much better:
def gcd(x, y):
while y != 0:
(x, y) = (y, x % y)
return x
Solution 3 - Python
This version of code utilizes Euclid's Algorithm for finding GCD.
def gcd_recursive(a, b):
if b == 0:
return a
else:
return gcd_recursive(b, a % b)
Solution 4 - Python
gcd = lambda m,n: m if not n else gcd(n,m%n)
Solution 5 - Python
using recursion,
def gcd(a,b):
return a if not b else gcd(b, a%b)
using while,
def gcd(a,b):
while b:
a,b = b, a%b
return a
using lambda,
gcd = lambda a,b : a if not b else gcd(b, a%b)
>>> gcd(10,20)
>>> 10
Solution 6 - Python
def gcd(m,n):
return gcd(abs(m-n), min(m, n)) if (m-n) else n
Solution 7 - Python
Very concise solution using recursion:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a%b)
Solution 8 - Python
a=int(raw_input('1st no \n'))
b=int(raw_input('2nd no \n'))
def gcd(m,n):
z=abs(m-n)
if (m-n)==0:
return n
else:
return gcd(z,min(m,n))
print gcd(a,b)
A different approach based on euclid's algorithm.
Solution 9 - Python
def gcdRecur(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
# Base case is when b = 0
if b == 0:
return a
# Recursive case
return gcdRecur(b, a % b)
Solution 10 - Python
I think another way is to use recursion. Here is my code:
def gcd(a, b):
if a > b:
c = a - b
gcd(b, c)
elif a < b:
c = b - a
gcd(a, c)
else:
return a
Solution 11 - Python
in python with recursion:
def gcd(a, b):
if a%b == 0:
return b
return gcd(b, a%b)
Solution 12 - Python
def gcd(a,b):
if b > a:
return gcd(b,a)
r = a%b
if r == 0:
return b
return gcd(r,b)
Solution 13 - Python
For a>b:
def gcd(a, b):
if(a<b):
a,b=b,a
while(b!=0):
r,b=b,a%r
a=r
return a
For either a>b or a<b:
def gcd(a, b):
t = min(a, b)
# Keep looping until t divides both a & b evenly
while a % t != 0 or b % t != 0:
t -= 1
return t
Solution 14 - Python
I had to do something like this for a homework assignment using while loops. Not the most efficient way, but if you don't want to use a function this works:
num1 = 20
num1_list = []
num2 = 40
num2_list = []
x = 1
y = 1
while x <= num1:
if num1 % x == 0:
num1_list.append(x)
x += 1
while y <= num2:
if num2 % y == 0:
num2_list.append(y)
y += 1
xy = list(set(num1_list).intersection(num2_list))
print(xy[-1])
Solution 15 - Python
def _grateest_common_devisor_euclid(p, q):
if q==0 :
return p
else:
reminder = p%q
return _grateest_common_devisor_euclid(q, reminder)
print(_grateest_common_devisor_euclid(8,3))
Solution 16 - Python
This code calculates the gcd of more than two numbers depending on the choice given by # the user, here user gives the number
numbers = [];
count = input ("HOW MANY NUMBERS YOU WANT TO CALCULATE GCD?\n")
for i in range(0, count):
number = input("ENTER THE NUMBER : \n")
numbers.append(number)
numbers_sorted = sorted(numbers)
print 'NUMBERS SORTED IN INCREASING ORDER\n',numbers_sorted
gcd = numbers_sorted[0]
for i in range(1, count):
divisor = gcd
dividend = numbers_sorted[i]
remainder = dividend % divisor
if remainder == 0 :
gcd = divisor
else :
while not remainder == 0 :
dividend_one = divisor
divisor_one = remainder
remainder = dividend_one % divisor_one
gcd = divisor_one
print 'GCD OF ' ,count,'NUMBERS IS \n', gcd
Solution 17 - Python
The value swapping didn't work well for me. So I just set up a mirror-like situation for numbers that are entered in either a < b OR a > b:
def gcd(a, b):
if a > b:
r = a % b
if r == 0:
return b
else:
return gcd(b, r)
if a < b:
r = b % a
if r == 0:
return a
else:
return gcd(a, r)
print gcd(18, 2)
Solution 18 - Python
#This program will find the hcf of a given list of numbers.
A = [65, 20, 100, 85, 125] #creates and initializes the list of numbers
def greatest_common_divisor(_A):
iterator = 1
factor = 1
a_length = len(_A)
smallest = 99999
#get the smallest number
for number in _A: #iterate through array
if number < smallest: #if current not the smallest number
smallest = number #set to highest
while iterator <= smallest: #iterate from 1 ... smallest number
for index in range(0, a_length): #loop through array
if _A[index] % iterator != 0: #if the element is not equally divisible by 0
break #stop and go to next element
if index == (a_length - 1): #if we reach the last element of array
factor = iterator #it means that all of them are divisibe by 0
iterator += 1 #let's increment to check if array divisible by next iterator
#print the factor
print factor
print "The highest common factor of: ",
for element in A:
print element,
print " is: ",
greatest_common_devisor(A)
Solution 19 - Python
def gcdIter(a, b):
gcd= min (a,b)
for i in range(0,min(a,b)):
if (a%gcd==0 and b%gcd==0):
return gcd
break
gcd-=1
Solution 20 - Python
Here's the solution implementing the concept of Iteration:
def gcdIter(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
if a > b:
result = b
result = a
if result == 1:
return 1
while result > 0:
if a % result == 0 and b % result == 0:
return result
result -= 1