[python] 최소공배수(LCM)

최소공배수란?

• 공배수(common multiple)란 두 수 이상의 공통된 여러 개의 배수를 의미한다.
• 최소공배수(LCM)란 두 수 이상의 공통된 여러 개의 공배수 중 최소인 수를 가리킨다.

1. 대표적인 방법

def lcm(a, b):
    for i in range(max(a, b), (a * b) + 1):
        if i % a == 0 and i % b == 0:
            return i

2. 최대공약수 활용방법

• 최소공배수 = (두 수의 곱) / 최대공약수

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
	return (a * b) / gcd(a, b)

or

import math

def lcm(a, b):
	return (a * b) / math.gcd(a, b)

3. 파이썬 math 라이브러리 방법

import math

a, b = 5, 10
math.lcm(a, b)

• 파이썬 3.9버전부터는 math 라이브러리를 사용하여 lcm을 바로 구할 수 있다.