Python code to find greatest common divisor of multiple numbers

Question

Hmm, I know this has been implemented countless times, and Python 3.9.5 math standard library has a built-in gcd() method that does exactly this, but this is how I do this, I think completing simple programming challenges using new ways will let gain experience that will help me find ingenious ways to overcome unprecedented practical programming challenges, so bear with me.

This implementation uses prime factorization method, it has three functions: factors(), gcd() and main(), the first function returns a dictionary object, the keys of the dictionary are the base prime factors of the inputted number, the values are the powers (how many times the factor should multiply by itself) of the keys, the dictionaries are created with one key{'1': 1};

And the second function accepts two numbers, uses each number as inputs to the first function, the compares the resultant dictionaries, removes keys of the first dictionary not contained in the second dictionary, and reduces the values of keys of the first dictionary to their respective values in the second dictionary if their values in first dictionary is greater than the second dictionary.

Then the second function gets the product of all keys ^ values of the first dictionary.

The third function applies gcd() recursively to the list of numbers if there are more than two numbers.

This is the code, it is fully functional, and works properly if the inputs are valid:

import math
import sys

def factors(n):
    factors = {'1': 1}
    f = 2
    while f <= int(math.sqrt(n)):
        while n % f == 0:
            if f'{f}' in factors.keys():
                factors.update({f'{f}': factors[f'{f}'] + 1})
            else:
                factors[f'{f}'] = 1
            n = int(n / f)
        f += 1
    if n > 1: factors[f'{n}'] = 1
    return factors

def gcd(x, y):
    f1 = factors(x)
    f2 = factors(y)
    for f in f1.copy().keys():
        if f not in f2.keys():
            f1.pop(f)
        elif f1[f] > f2[f]:
            f1[f'{f}'] = f2[f]
    cd = 1
    for f in f1.keys():
        cd *= int(f) ** f1[f]
    return cd

def main(args):
    args = list(map(int, args))
    cd = gcd(args[0], args[1])
    if len(args) > 2:
        for i in args[2:]:
            cd = gcd(cd, i)
    print(cd)

args = sys.argv[1:]
main(args)

Currently I think two areas need be improved:

1, I need a better way than dictionaries to keep track of the divisors, so that I can easily find divisors not contained in the other number and find the lower power of the same divisor.

2, make the gcd() function do what main() function does internally so that the main() function isn't needed, currently I can't figure out a way to do this.

How can this script be improved?

Answer 1

It's more common to use Euler's method to find GCD, rather than factorising both numbers. However, I'll continue reviewing with the existing algorithm, as there's useful insights to be found.

---

First, let's look at factors().

Our factors variable is being used as a counter or multiset, and Python provides us with a collections.Counter class for that.

With from collections import Counter, we can replace

        if f'{f}' in factors.keys():
            factors.update({f'{f}': factors[f'{f}'] + 1})
        else:
            factors[f'{f}'] = 1

with

        factors[f] += 1

(I've also changed to using the numbers themselves as keys, instead of converting to string).

The division int(n / f) can be rewritten using integer divide operator n // f (and we know the result will be exact, as we tested n % f == 0). Also, we should use math.isqrt() rather than int(math.sqrt()) when we want an integer.

from collections import Counter

def factors(n):
    factors = Counter({1: 1, n: 1})
    for f in range(2, 1 + math.sqrt(n)):
        while n % f == 0:
            factors[f] += 1
            n = n // f
    return factors

---

Now let's look at gcd().

We are computing the intersection of the two multisets. The operator & does exactly that for us:

common_factors = f1 & f2
cd = 1
for f in common_factors.keys():
    cd *= f ** common_factors[f]

When we iterate over a dictionary, we don't need to get the keys and then index again. We can iterate over its items() instead, like this:

for f,count in common_factors.items():
    cd *= f ** count

Or we could expand the multiset using elements():

for f in common_factors.elements():
    cd *= f

This allows us to then use math.prod() instead of our own loop:

return math.prod(common_factors.elements())

The whole lot then becomes a one-liner:

def gcd(x, y):
    return math.prod((factors(x) & factors(y)).elements())

---

Next, main(). The heart of this function is what a functional programmer would call reduce, and - you guessed it - Python provides a reduce() function, in functools:

def main(args):
    args = map(int, args)
    print(reduce(gcd, args))

---

Finally, it's good practice to use a main guard, so the program can become a module:

if __name__ == "__main__":
    args = sys.argv[1:]
    main(args)

---

Simplified code

import math
import sys
from collections import Counter
from functools import reduce

def factors(n):
    factors = Counter({1: 1, n: 1})
    for f in range(2, int(math.sqrt(n))):
        while n % f == 0:
            factors[f] += 1
            n = n // f
    return factors

def gcd(x, y):
    return math.prod((factors(x) & factors(y)).elements())

if __name__ == "__main__":
    print(reduce(gcd, map(int, sys.argv[1:])))