[백준] 2609 최대공약수와 최소공배수 (Python)

이런! 최소공배수가 뭔지 기억이 안 날 뻔 했다. 심각한 수학 실력... 수학 포기하지 말걸~~~,,, 컴퓨터 공학과를 꿈꾸는 청소년 여러분 수학 포기하지 마세요 제발... 최대 공약수는 유클리드 호제법으로 구할 수 있다. 유클리드 호제법은 나누고 나눈 수를 나머지로 나누는 알고리즘이다.

유클리드 호제법

먼저 큰 수를 작은 수로 나눈 나머지를 구한다. 그 다음 나눴던 수를 나머지로 또 나누어 나머지를 구한다. 나머지가 0 이 되었을 때 마지막 계산에서 나누는 수로 사용된 숫자가 두 수의 최대공약수가 된다.

 

이를 반복문과 재귀함수로 구현할 수 있다. 

# 반복문
def gcd(a,b) :
    while b != 0 :
        a, b = b, a % b
    return a

# 재귀 함수
 def gcd (a,b) :
     if b == 0 :
         return a
     return gcd(b, a % b)

n, m = map(int, input().split())

def gcd(a,b) :
    while b != 0 :
        a, b = b, a % b
    return a
    
def lcm(a,b) :
    return a * b // gcd(a,b)
    
print(gcd(n,m))
print(lcm(n,m))