최대공약수와 최소공배수

들어가며

안녕하세요, 이번 포스팅에서는 지난 포스팅에 배웠던 소인수 분해를 이용해서
최대공약수와 최소공배수를 구하는 프로그램을 만들어보도록 하겠습니다.
먼저, 최대공약수의 개념에 대해서 확인해보겠습니다.

최대공약수(GCD)

최대공약수는 두 수 또는 그 이상의 수에서 공통으로 나눌 수 있는 가장 큰 수를 의미합니다.
공약수가 두 수 또는 그 이상의 수에서 공통으로 나눌 수 있는 수를 뜻하기 때문에,
'최대'공약수는 그 중에서 가장 큰 수라고 볼 수 있겠습니다.

• ex) 12와 18의 최대공약수는 6인데, 이는 12와 18을 공통으로 나눌 수 있는 가장 큰 수는 6이기 때문입니다.

최소공배수(LCM)

최소공배수는 두 개 이상의 수의 배수들 중 공통으로 포함된 가장 작은 배수를 의미합니다.
공배수는 두 개 이상의 배수들 중에서 공통으로 포함된 배수를 뜻하기 때문에
'최소'공배수는 그 중에서 가장 작은 수를 의미합니다.

• ex) 12와 18의 최소공배수는 36인데, 이는 12와 18의 배수 중 가장 작은 배수는 36입니다.

소인수분해를 이용해서 구하기

최대공약수와 최소공배수는 소인수분해를 통해서 구할 수 있습니다.
해당 과정을 지난 시간에 작성했던 is_prime 함수와 prime_factorization 함수를 이용해서 작성해보겠습니다.
해당 함수는 https://endure-life.tistory.com/47 소인수분해편을 참조해주세요.

최대공약수

1. 두 수의 소인수분해를 구합니다
2. 두 수의 공통된 소인수를 찾아 공통된 소인수의 곱을 구합니다.
 - 예를 들어 두 수의 소인수가 (2,2,3), (2,2,3,3)일 경우, 공통된 소인수는 (2,2,3)입니다.

최대공약수 code

def gcd(a, b):
    # 두 수의 소인수분해를 구합니다
    factors_a = prime_factorization(a) 
    factors_b = prime_factorization(b)

    # 두 수의 공통된 소인수를 찾고, 
    common_factors = list(set(factors_a) & set(factors_b))
    gcd_value = 1

    # 공통된 소인수의 곱을 구합니다.
    for factor in common_factors:
        gcd_value *= factor ** min(factors_a.count(factor), factors_b.count(factor))
    return gcd_value

최소공배수

1. 두 수의 소인수 분해를 구합니다
2. 두 수의 모든 소인수를 모으고, 각 소인수를 각 소인수의 최대 갯수만큼 곱합니다.

최소공배수 code

def lcm(a, b):
    # 두 수의 소인수 분해를 구합니다.
    factors_a = prime_factorization(a)
    factors_b = prime_factorization(b)

    # 두 수의 모든 소인수를 모읍니다
    all_factors = list(set(factors_a) | set(factors_b))
    lcm_value = 1

    # 각 소인수의 최대 개수만큼 곱합니다.
    for factor in all_factors:
        lcm_value *= factor ** max(factors_a.count(factor), factors_b.count(factor))
    return lcm_value

지난 시간의 소인수분해에 이어, 소인수분해를 이용한 최대공약수와 최소공배수를 구해보았습니다.
이 방법은 작은 숫자들에서는 잘 작동하지만, 숫자들이 조금만 커져도 시간이 꽤 많이 걸립니다.
때문에 이런 방법을 해결하기 위해 고안된 알고리즘이 '유클리드 호제법'입니다.
하지만 이 알고리즘은 중등과정에 포함되지 않기 때문에 여기서는 다루지 않고, 차후에 기회가 된다면 다뤄보도록 하겠습니다.

혹시나 관심이 있으신 분들은 댓글 달아주시면 감사하겠습니다.
오늘도 읽어주셔서 감사합니다. 좋은 하루되세요.