Code for Greatest Common Divisor in Python

Question

The greatest common factor (GCD) a and b is the largest number that divides them both without a remainder.

One way to find the GCD of two numbers is the Euclidean algorithm, based on the observation that if r is the remainder when a is divisible by b , then gcd(a, b) = gcd(b, r) . As the base case, we can use gcd(a, 0) = a .

Write a gcd function that takes a and b and returns their largest common divisor.

Answer 1

This is in the standard library .

 >>> from fractions import gcd >>> gcd(20,8) 4 

Source code from 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 

Starting with Python 3.5, gcd is in the math module ; one in fractions deprecated. Moreover, inspect.getsource no longer returns explanatory source code for both methods.

Answer 2

Algorithms with mn can work for a very long time.

This is much better:

 def gcd(x, y): while y != 0: (x, y) = (y, x % y) return x 

Answer 3

This version of the code uses the Euclidean algorithm to find the GCD.

 def gcd_recursive(a, b): if b == 0: return a else: return gcd_recursive(b, a % b) 

Answer 4

 gcd = lambda m,n: m if not n else gcd(n,m%n) 

Answer 5

 def gcd(m,n): return gcd(abs(mn), min(m, n)) if (mn) else n 

Answer 6

A very concise solution using recursion:

 def gcd(a, b): if b == 0: return a return gcd(b, a%b) 

Answer 7

using recursion

 def gcd(a,b): return a if not b else gcd(b, a%b) 

using time

 def gcd(a,b): while b: a,b = b, a%b return a 

using lambda

 gcd = lambda a,b : b, gcd(a%b) >>> gcd(10,20) >>> 10 

Answer 8

 a=int(raw_input('1st no \n')) b=int(raw_input('2nd no \n')) def gcd(m,n): z=abs(mn) if (mn)==0: return n else: return gcd(z,min(m,n)) print gcd(a,b) 

Another approach based on the Euclidean algorithm.

Answer 9

 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) 

Answer 10

in python with recursion:

 def gcd(a, b): if a%b == 0: return b return gcd(b, a%b) 

Answer 11

 def gcd(a,b): if b > a: return gcd(b,a) r = a%b if r == 0: return b return gcd(r,b) 

Answer 12

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 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 

Answer 13

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 

Answer 14

Here is a solution that implements the Iteration concept:

 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 

Answer 15

I should have done something similar for homework using while loops. Not the most efficient way, but if you do not want to use the 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]) 

Answer 16

 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)) 

Answer 17

This code calculates gcd of more than two numbers, depending on the choice given by the user, here the 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 

Answer 18

The exchange of meaning did not help me. So I just created a mirror situation for numbers that are entered either in <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) 

Answer 19

 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 

Answer 20

 #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 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)