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?