Calculating GCD - how to check every element in list

Question

• Multiple number inputs

below is just how I chose to start writing my code

def main():

numbers = input()
if numbers == "0":
    exit()
else:
    number_list = [int(i) for i in numbers.split()]

def calculate_gcd(number_list):
    for i in range(1,smallest_number(number_list)+1):
        for n in range(0,len(number_list)):
            if number_list[n] % i == 0:
               check_list += number_list[n]

more code - but not important for the question im asking
my code was hardly complete and only worked for max 3 size lists, sadly.

How I thought of logic

1. Read input -> split by space, put it in list
2. sort the list
3. make a variable (divisor), and set it to 1
4. while divisor <= sortedlist[0] (which is smallest in list) 5. if every element % divisor == 0, then gcd = divisor, then divisor+=1
5. loop until it is no longer true

Problem I found

1. It requires stupid effort, it will actually not run and give runtime error.
2. I'm having trouble finding a way to check No.5 (in bold) I know that there is gcd function, but it only deals with two inputs. and it comes down to same question, how do I make sure 'all' elements divides down to zero?

Any suggestion of making gcd logic and comment on No.5 (bold) ?

Thank you

Answer 1

Instead of tackling the bigger problem, why not tackle a smaller problem. How do you find the gcd of two numbers? Well, there are multiple algorithms for this. Let us use the iterative one:

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

Now, one thing to realize is that, if you have multiple numbers, and you want to find the gcd of all numbers, then it is simply:

gcd(gcd(...(a, b), c), ...)

In simpler terms, if you want to find the gcd of three numbers (a, b, c), then you would do the following:

gcd = gcd_iterative(a, b) 
gcd = gcd_iterative(gcd, c)

So, now if you have a list of numbers, lst, you can do the following:

>>> gcd = lst[0]
>>> for num in lst[1:]:
        gcd = gcd_iterative(gcd, num)
>>> print(gcd)