파이썬 두 수의 최소공배수

최소공배수는 두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수를 뜻한다.

파이썬 코드로 구현해보면 

a, b = map(int, input().split())

for i in range(1, a * b + 1):

    if i % a == 0 and i % b == 0:

       

        print(i)

        break

위와 같이 간단하게 구할 수 있다. 하지만 해당 코드는 숫자가 커질수록 코드의 효율이 떨어진다.

 

최소공배수를 빠르게 찾기 위해선 유클리드 호제법을 사용할 수 있다.

유클리드 호제법이란 간단히 말해 두 수의 최대 공약수를 구하는 방법이다.

자세히 말하면 두 정수 (a > b > 0)에 대하여 a = bq + r (0 <= r < b)(a를 b로 나눈 나머지가 r 일때) 이라면

a, b의 최대공약수는 b,r의 최대공약수와 같는 법칙이다.

def gcd(a, b): #최대공약수

    while b:

        a, b = b, a % b

    return a

코드로 구현하면 위와 같다.

 

최대공약수는 두 수 a, b에 대해서 a, b의 곱을 최대 공약수로 나눈 값이다.

def lcm(a, b): #최소공배수

    return a * b // gcd(a, b)

코드로 구현하면 위와 같다.

 

위 두 함수를 이용하여 두 수의 최소공배수를 구하는 코드는 아래와 같다.

def gcd(a, b): #최대공약수

    while b:

        a, b = b, a % b

    return a

def lcm(a, b): #최소공배수

    return a * b // gcd(a, b)

a, b = map(int, input().split())

result = lcm(a, b)

print(result)

위처럼 코드 작성시 효율성까지 고려하여 작성할 수 있다.