[Algorithm] 유클리드의 호제법은 뭐야?

두 정수 또는 두 정식인 a와 b가 있을 때, a를 b로 나눈 나머지 a'로 b를 나누고 그 나머지로 a'를 나누는 일을 완전히 나누어질 때까지 계속하여 a와 b의 최대 공약수를 구하는 방법. 단, a, b가 자연수일 때 a>b, 다항식일 때는 a의 차수가 b의 차수 이상이어야 한다. - 네이버 '유클리드의 호제법' 사전 정의

 

위의 정의에서는 아래의 조건이 만족해야 한다.

• a, b는 자연수이다.
• a > b가 만족한다.

유클리드의 호제법은 다음의 과정을 실행한다. a, b는 자연수(a > b), value = a % b이다.

• b!= 0 이 되기 전까지 a % b 연산을 실행한다.
• a에 b의 값을 대입하고, b에 value값을 대입한다.
• 1의 과정을 반복한다.

다음은 위의 과정을 그림으로 표현한 것이다.

 

다음의 예제를 통해서 '유클리드의 호제법'의 활용을 알아보겠다. 문제 해설

2609번: 최대공약수와 최소공배수

해당 문제는 최대공약수(value)는 유클리드의 호제법을 사용하고, 최소공배수는 두 개의 자연수(a, b)를 곱한 값에서 최대공약수를 나누어주는 방법으로 해결한다.

 

최소공배수: a * b // value 연산을 통해서 해결한다.

 

위의 과정을 코드로 옮기면 다음과 같다.

 

def Euclidean(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    
    return a
 
a, b = map(int, input().split())
value = Euclidean(a, b)
print(value)
print(a * b // value)