Least common multiple and greatest common divisor

Least common multiple and greatest common divisor.md

Least common multiple and greatest common divisor

Below is some code for calculating the least common multiple and greatest common divisor. This could be made more efficient in several ways, for example, using a prime number sieve (as demonstrated in one of my other Gists) instead of trial division to build up a prime factorisation:

from math import sqrt, log, exp
import numpy as np


def divides(factor, x):
    if x % factor == 0:
        return True
    else:
        return False

def add_factor(x, factor_dict, factor):
    if factor not in factor_dict:
        factor_dict[factor] = 1
    else:
        factor_dict[factor] += 1
    return x // factor, factor_dict

def prime_factorisation(x):
    factor_dict = dict()
    max_factor = int(sqrt(x))
    while divides(2, x):
        x, factor_dict = add_factor(x, factor_dict, 2)
    for i in range(3, max_factor + 1, 2):
        while divides(i, x):
            x, factor_dict = add_factor(x, factor_dict, i)
        if x == 1:
            break
    if x != 1:
        factor_dict[x] = 1
    return factor_dict

def lowest_common_multiple(a, b):
    a_fd = prime_factorisation(a)
    b_fd = prime_factorisation(b)
    fd_list = [a_fd, b_fd]
    factor_set = set(i for fd in fd_list for i in fd.keys())
    max_power = lambda k: max(
        d.get(k) for d in fd_list if d.get(k) is not None
    )
    factor_dict = {i: max_power(i) for i in factor_set}
    lcm = 1
    for factor, power in factor_dict.items():
        lcm *= (factor ** power)
    return lcm

def greatest_common_divisor(a, b):
    a_fd = prime_factorisation(a)
    b_fd = prime_factorisation(b)
    fd_list = [a_fd, b_fd]
    factor_set = set(a_fd.keys()) & set(b_fd.keys())
    min_power = lambda k: min(
        d.get(k) for d in fd_list if d.get(k) is not None
    )
    factor_dict = {i: min_power(i) for i in factor_set}
    gcd = 1
    for factor, power in factor_dict.items():
        gcd *= (factor ** power)
    return gcd

if __name__ == "__main__":
    for a, b in [(32, 240), (8642, 2648)]:
        print(prime_factorisation(a))
        print(prime_factorisation(b))
        print(lowest_common_multiple(a, b))
        print(greatest_common_divisor(a, b))

Output:

{2: 5}
{2: 4, 3: 1, 5: 1}
480
16
{2: 1, 29: 1, 149: 1}
{2: 3, 331: 1}
11442008
2