[Python] BOJ 2609 - 최대공약수와 최소공배수(유클리드 호제법)

https://www.acmicpc.net/problem/2609

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

* 유클리드 호제법이란?

출처 : 네이버 지식백과

- 즉, a,b의 최대공약수는 b,r의 최대공약수와 같다는 것이다.

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

- 따라서 b가 0이 아닌 동안 b를 a에 넣고 a를 b로 나눈 나머지를 b에 넣는 과정을 반복했다.

 

- 9번째 줄은 최대공약수 출력이고, 마지막 줄에는 최소공배수 출력인데

최소공배수는 두 수를 곱한 것을 최대공약수로 나누어주면 된다.