[백준] 2609 최대공약수와 최소공배수 - python

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

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

 

이번 기회에 파이썬에서 사용 가능한 최대공약수(gcd), 최소공배수(lcm) 구하는 방법을 다 정리해보았다.

 

가장 베이직한 방법

최대공약수 : 숫자 x,y 중 더 작은 숫자부터 1까지 -1 해가며 x%i == 0 and y%i == 0인 숫자 찾기

최소공배수 : 숫자 x,y 중 더 큰 숫자부터 (x*y)까지 +1 해가며 i%x == 0 and i%y == 0인 숫자 찾기

 

유클리드 호제법

x,y의 gcd는 y와 r의 gcd와 같다. ( x%y = r)

 

즉 계속해서 x의 자리에 y값을 대입하고, y에는 x%y 값인 r을 대입하면 x%y == 0 인 순간의 y값이 바로 gcd이다.

 

최소공배수는 x*y를 위에서 구한 gcd로 나눠주면 된다.

 

라이브러리 활용

이게 사실 제일 편하다..^^ 파이썬의 math 라이브러리는 인자를 심지어 여러개 받을 수 있는 최대공약수, 최소공배수를 구해주는 함수를 제공한다.

math 라이브러리를 import 해주고 math.gcd( 인자, 인자, ... ) math.lcm( 인자, 인자 ,... ) 해주면 된다.

 

 

코드는 다음과 같다.

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

# 가장 베이직한 방법
def getGCD_basic(x, y):
    for i in range(min(x, y), 0, -1):
        if x % i == 0 and y % i == 0:
            return i


def getLCM_basic(x, y):
    for i in range(max(x, y), (x * y) + 1):
        if i % x == 0 and i % y == 0:
            return i


# 유클리드 호제법
def getGCD_euclid(x, y):
    while y:
        x, y = y, x % y
    return x


def getLCM_euclid(x, y):
    return (x * y) // getGCD_euclid(x, y)


# 파이썬 라이브러리 활용
import math

print(math.gcd(n, m))
print(math.lcm(n, m))

 

유클리드 호제법은 정말... 정말 오랜만에 다시 들여다봤다...^^ 수학을 열심히 했던 학생이었는데 이렇게까지 싸그리 까먹을 수 있다니 슬프다. 안 좋은 일이나 빨리 까먹지 이런 수학적 지식만 홀라당 다 까먹어 버렸다.