Python gcd for list

Question

I want to calculate gcd for a list of numbers. But I don't know what's wrong with my code.

A = [12, 24, 27, 30, 36]


def Greatest_Common_Divisor(A):
    for c in A:
        while int(c) > 0:
            if int(c) > 12:
                c = int(c) % 12
            else:
                return 12 % int(c)
    print Greatest_Common_Divisor(A)

Answer 1

As of python 3.9, python got built-in support for calculating gcd over a list of numbers.

import math
A = [12, 24, 27, 30, 36]
print(math.gcd(*A))

Output:

3

Answer 2

If you'd like to use an existing method try `np.gcd.reduce':

import numpy as np

A = [12, 24, 27, 30, 36]

print(np.gcd.reduce(A))

which returns 3

Answer 3

def find_gcd(l):
    def gcd(a, b):
        while b:
            a, b = b, a%b
        return a
    n =1
    f = l[0]
    while n != len(l):
        f = gcd(f,l[n])
        if  f == 1:
            return 1
        else:
            n = n + 1          
    return f

l = [12, 24, 27, 30, 36]
print(find_gcd(l))

Answer 4

gcd of a list input by the user which can be used for any number of input values.

 n = int(input('enter no of numbers: '))
a = list(map(int,input('enter numbers to find gcd: ').strip().split()))[:n]

def gcd(num1,num2):
    x = 1
    while x:
        if max(num1,num2) % min(num1,num2) == 0:
            return min(num1,num2)
            x = 0
        else :
            r = max(num1,num2)%min(num1,num2)
            return gcd(max(num1,num2),r)

while True:
        a[0] = gcd(a[0],a[1])
        a.pop(1)
        if len(set(a))>2:
            a.pop(2)
        if len(set(a)) == 1:
            break
a = set(a)
print(a)

Answer 5

I used this piece of code:

def gcd(my_list):
    result = my_list[0]
    for x in my_list[1:]:
        if result < x:
            temp = result
            result = x
            x = temp
        while x != 0:
            temp = x
            x = result % x
            result = temp
    return result 

Answer 6

import functools as f
A = [12, 24, 27, 30, 36]
g = lambda a,b:a if b==0 else g(b,a%b)   #Gcd for two numbers
print(f.reduce(lambda x,y:g(x,y),A))     #Calling gcd function throughout the list.

"Lambda" is an anonymous function where 'g' is assigned with GCD of two numbers whenever called.

"Reduce" is a function in "functools" module which is used to perform a particular function to all of the elements in the list. Here reduce() computes the GCD of the complete list A by computing GCD of first two elements, then the GCD of 3rd element with previously computed GCD of first two elements and so on.

Hope this clears your doubt.

Answer 7

here is the piece of code, that I used:

from fractions import gcd
from functools import reduce
def find_gcd(list):
    x = reduce(gcd, list)
    return x

Answer 8

from functools import reduce
def gcd(a,b):
    if a==0:
        return b 
    else:
        return gcd(b%a,a)
A = [12, 24, 27, 30, 36]
gcdp = reduce(lambda x,y:gcd(x,y),A)
print(gcdp)

I guess this one will clear your doubts.

Answer 9

def gcd (a,b):
    if (b == 0):
        return a
    else:
         return gcd (b, a % b)
A = [12, 24, 27, 30, 36]
res = A[0]
for c in A[1::]:
    res = gcd(res , c)
print res

ideone link

Answer 10

It's not clear to me why you are using 12 in your function? Do you want to test your algorithm with 12 specifically?

There is built in function that provides a good solution (fraction.gcd()) as referenced in this answer

If you want to develop your own approach, you could do it this way: sort the list and get the minimum number of list (call it min). Loop from 2 to min, you can get the great common divisor of your list.

Answer 11

As I see your code will simply go in infinite loop. Since you call method Greatest_Common_Divisor recursively but without base case. Align print Greatest_Common_Divisor(A) and "def" in the same column and that problem would be solved. But still what your code does for each number ai, it takes remainder of ai % 12, and then simply print 12 % (ai % 12), and there is no any connection between it and greatestCommonDivisor. Here is simple code for gcd(a,b) which you can use for the whole array:

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

Answer 12

return exits the function. Inside a for-loop this is normally not intended.