#9 정수론 - 최대공약수와 최소공배수

 코딩테스트의 문제들을 풀다보면 어느정도의 수학적 지식을 요구하는 문제들이 종종 등장한다.  이번에는 그 중에도 최대공약수(GCD)와 최소공배수(LCM)에 대해 알아본다. 

 

1. 최대공약수(Greatest Common Divisor)

 어떤 두 수의 최대공약수는 두 수의 공통 약수중 가장 큰 것이다.  단순히 두 수중 작은쪽부터 시작해서 수를 점점 줄여나가며 처음으로 발견되는 공통 약수를 구하는 방법도 있지만 이 방법은 숫자의 크기가 크고 최대공약수가 작을수록 굉장히 많은 시간을 소요한다.   최대공약수를 보다 빠르고 간단하게 구하는 방법으로 유클리드 호제법이 있다. 

 

① 두 수중 큰 쪽을 A, 작은 쪽을 B라고 한다.

② A가 B로 나누어 떨어진다면 B가 두 수의 최대공약수이다.

③ 나누어 떨어지지 않는다면 A를 B로 나눈 나머지 C를 구한다

④ A = B,  B = C 로 한 뒤 ②번으로 돌아간다.

 

 

2. 최소공배수(Least Common Multiple)

 어떤 두 수의 최소공배수는 두 수의 공통 배수중 가장 작은 것이다.  최대공약수를 구하는 법을 안다면 최소공배수를 구하는 것은 매우 간단하다. 두 수를 곱한 뒤 최대공약수로 나누면 된다.  

 

 

이를 이용하여 최소공배수, 최대공약수를 구하는 문제(https://www.acmicpc.net/problem/2609)를 해결한 코드는 다음과 같다.

import sys


def sol2609():
    n, m = map(int, sys.stdin.read().split())
    # 1
    if n < m:
        n, m = m, n
    gcd = [n, m]
    # 2
    while gcd[1] != 0:
    	# 3, 4
        gcd = [gcd[1], gcd[0] % gcd[1]]
        
    print(gcd[0], n * m // gcd[0], sep='\n')
   

if __name__ == '__main__':
    sol2609()