[알고리즘] 최대 공약수, 최소 공배수

오늘은 파이썬의 기초중의 기초! 최대 공약수와 최소 공배수를 풀어보자!!

 

최대 공약수(Greatest Common Divisor)는 공약수 중에 가장 큰 수 이다.  공약수는 동시에 그들 모두의 약수인 정수이다. 

최소 공배수(Least Common Multiple)는  공배수 중에 가장 작은 수 이다. 공배수는 동시에 그들 모두의 배수인 정수이다. 

 

1. 최소 공배수 GCD(Greatest Common Divisor)

 

유클리드 호제법이란?

2개의 자연수(또는 정식) a, b 최대공약수는 b와 a-b의 최대공약수와 같다. (a>b)

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

def GCD():
    a,b = map(int, input().split())

    # 나머지가 0일때 까지 반복
    while b != 0:
        a,b = b, a % b

    return a

위의 코드가 유클리드 호제법으로 최대 공약수를 구할 수 있는 코드이다. (a <= b 인 경우)

유클리드 호제법에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여

나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

 

 

2. 최소 공배수 GCD(Greatest Common Divisor)

 

최대 공약수 로직을 알면 최소 공배수도 쉽게 구할 수 있다.

def LCM():
    a, b = map(int, input().split())
    A, B = a, b

    while b != 0:  # 유클리드 호제법
        a, b = b, a % b

    return (A*B//a)

최소 공배수는 2개의 자연수의 곱 / 최대 공약수 이므로 유클리드 호제법으로 구한 최대 공약수를 이용하여 구할 수 있다.