얌생

유클리드 호제법은 '2개의 자연수 a, b에 대해 a를 b로 나눈 나머지를 r이라 하면 ( 단, a > b ),

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.' 라는 성질을 활용해 두 수의 최대공약수 ( GCD )를 구하는 방법이다.

최대 공약수 ( GCD ) 구하기

• a와 b를 나눈 나머지를 r이라고 하자. ( a >= b , 0 <= r < b )
• a와 b의 최대공약수를 ( a, b ) 라고 하면, 다음이 성립한다.
• ( a, b ) = ( b, r )
• 위의 방식으로 나머지가 0이 될 때까지 반복하면 최대 공약수를 구할 수 있다.

function FindGcd(a, b) {
    var remainder = a % b;
    if (remainder == 0) {
        return b;
    }

    return FindGcd(b, remainder);
}

최소 공배수( LCM ) 구하기

a, b에 대해서 최소 공배수와 최대 공약수는 a * b = GCD * LCM 을 만족한다.

따라서 최소 공배수 ( LCM )는 a * b / GCD를 사용해 구할 수 있다.

var lcm = (a * b) / findGcd(a,b);

출처

•  https://ko.wikipedia.org/wiki/유클리드_호제법