유클리드 알고리즘 (Euclidean Algorithm)

📌 유클리드 호제법

일반적인 최대공약수를 구하는 방법은 두 수의 공통 약수를 모두 구해 곱하는 방법입니다.

100과 40의 최대공약수를 다음과 같이 구할 수 있습니다.

100 = 2^2 * 5^2
40 = 2^3 * 5
------------------------
최대공약수 = 2^2 * 5 = 20

 

유클리드 호제법은 일반적인 방법과는 좀 다른 방법으로 두 수의 최대공약수를 구합니다.

유클리드 호제법은 다음과 같이 구할 수 있습니다.

 

먼저 큰 수를 작은 수로 나눈 나머지를 구합니다.

100 % 40 = 20 (%는 나머지를 구하는 연산자)

 

 

그 다음 나눴던 작은 수를 나머지로 다시 나누고 나머지를 구합니다. 나머지가 0이 될 때까지 이 과정을 반복합니다.

나머지가 0이 되었을 때, 마지막으로 나눈 수가 최대공약수가 됩니다. 따라서, 여기서는 20이 최대공약수가 됩니다.

 

40 % 20 = 0

 

최소공배수는 두 수의 곱을 두 수의 최대공약수로 나누면 됩니다.

최소공배수 = (100 * 40) / 20

 

 

📌 코드

재귀

def get_gcd(a, b):
    if b == 0:
        return a

    if a % b == 0:
        return b

    return get_gcd(b, a % b)


def gcd_lcm(n, m):
    max_num, min_num = max(n, m), min(n, m)
    gcd = get_gcd(max_num, min_num)

    return f'최대공약수: {gcd}, 최소공배수: {int((n * m) / gcd)}'
    

print(gcd_lcm(100, 40))  # 최대공약수: 20, 최소공배수: 200

 

반복문

def get_gcd(a, b):
    temp = 1

    while temp > 0:
        temp = a % b
        a, b = b, temp

    return a


def gcd_lcm(n, m):
    max_num, min_num = max(n, m), min(n, m)
    gcd = get_gcd(max_num, min_num)

    return f'최대공약수: {gcd}, 최소공배수: {int((n * m) / gcd)}'
    

print(gcd_lcm(100, 40))  # 최대공약수: 20, 최소공배수: 200

 

 

관련문제

프로그래머스 최대공약수와 최소공배수

프로그래머스