MDC

mdc.py

# MDC Maximo Divisor Comum: Maior número que é divisor de dois ou mais números simultaneamente
# Input: Lista separada por virgula com os numeros a serem testados
# Output: Número divisor

from operator import mul
from functools import reduce

def get_prime_list(n: int) -> list:
    # Sieve of Erastothenes
    is_prime_list = {}

    for i in range(2, n + 1):
        is_prime_list[i] = True

    for key in is_prime_list.keys():
        for number in is_prime_list.keys():
            if key != number and is_prime_list[number]:
                if number % key == 0:
                    is_prime_list[number] = False

    return [key for key in is_prime_list.keys() if is_prime_list[key]]

def mdc(numbers: list) -> int:
    numbers_ordered = sorted(numbers, reverse=True)

    largest_number = numbers_ordered[0]

    prime_list = iter(get_prime_list(largest_number))
    common_divisors = []
    prime_number = next(prime_list)

    while True:
        next_prime = []
        if sum(numbers_ordered) == len(numbers_ordered):
            break
        for index, number in enumerate(numbers_ordered):
            if number % prime_number == 0:
                next_prime.append(False)
                numbers_ordered[index] = number // prime_number
            else:
                next_prime.append(True)
        if not any(next_prime):
            common_divisors.append(prime_number)
        elif all(next_prime):
            prime_number = next(prime_list)
    return reduce(mul, common_divisors)

assert mdc([20, 24]) == 4
assert mdc([18, 60]) == 6
assert mdc([6, 12, 15]) == 3
assert mdc([150, 120]) == 30
assert mdc([320, 400]) == 80