[알고리즘/파이썬] 백준 2609번 - 최대공약수와 최소공배수

 

 

 

 

 

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

 

 최대공약수를 구하는 여러방법이 있는데 가장 유명한것은 유클리드 호제법. 단번에 이해되는 예시도 있으니 아래의 백과사전을 참고하자.

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

 

최대공약수를 먼저 구하면 최소공배수는 쉽게 구할 수 있다. 이유는 최대공약수와 최소공배수는 아래와 같은 관계를 가지기 때문이다.

 

 

위의 원리를 따라서 코드를 구현했다.

먼저 최대공약수(G)를 구하도록 했다. 최대공약수가 도출되면 이를 이용해서 최소공배수를 구했다. 

a = list(map(int,input().split()))
a.sort()
b = a.copy()

while True:
    if a[1] % a[0] == 0 :
        print(a[0]) # 최대공약수
        ans = a[0]
        for n in b:
            ans = ans * int(n/a[0])
        print(ans) # 최소공배수
        break

    else:
        a[1] = a[1] % a[0]
    a.sort()