[JS/TS] 두 수의 최대공약수 최소공배수 알고리즘 (GCD, LCM)

두 수를 입력받아서 두 수의 최대공약수와 최소 공배수를 구해보자

 

최대공약수

const getGCD = (num1, num2) => {
    let bigNum = Math.max(num1, num2);
    let smallNum = Math.min(num1, num2);
	// smallNum이 0이 될떄까지
    while(smallNum > 0) {
        // 큰 수를 작은수로 나눈 나머지는 r
        let r = bigNum % smallNum;
        // 큰 수에 작은수를 대입
        bigNum = smallNum;
        // 작은 수에 r을 대입
        smallNum = r;
    }
    // bigNum이 최대공약수
    return bigNum;
}

최소공배수

위 최대공약수 알고리즘을 통해 구한 최대공약수로 두 수의 곱을 나눠주면 최소 공배수 이다.

const getLCD = (n, m) => {
    const gcd = getGCD(n, m)
    return (n * m) / gcd;
}