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.
This question is related to
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
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)
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
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
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))
gcd = lambda m,n: m if not n else gcd(n,m%n)
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
in python with recursion:
def gcd(a, b):
if a%b == 0:
return b
return gcd(b, a%b)
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.
def gcd(a,b):
if b > a:
return gcd(b,a)
r = a%b
if r == 0:
return b
return gcd(r,b)
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])
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)
Very concise solution using recursion:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a%b)
#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)
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
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
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
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
def gcd(m,n):
return gcd(abs(m-n), min(m, n)) if (m-n) else n
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.
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)
Source: Stackoverflow.com