최소 공배수란?
2개 이상의 수의 공배수 중 가장 작은 수
5의 배수 : 5, 10, 15, 20. 25, 30. 35, 40...
7의 배수 : 7, 14, 21, 27, 35, 42...
5와 7의 최소 공배수 = 35
식으로 나타내면
f(X, Y)는 정수 X와 Y의 최소 공배수
G는 정수 X와 Y의 최대 공약수
라고 할때
f(X, Y) = (X × Y) / G
이다
물론, 이러한 수학식을 몰라도
최소 공배수를 구할 수 있다.
하지만 최대 공약수와 위의 식을 활용하면
조금 더 효율적으로 최소 공배수를 구할 수 있다.
최대 공약수는 유클리드 호제법을 활용하면 쉽게 구할 수 있다.
'알고리즘 > 기타 알고리즘' 카테고리의 다른 글
하노이탑 알고리즘(Tower of Hanoi Algorithm) (0) | 2017.02.12 |
---|---|
피보나치 수열(Fibonacci Numbers) (0) | 2017.02.08 |
최대 공약수(Greatest Common Divisor) (0) | 2017.02.07 |