최대공약수, 최소공배수, 유클리드 호제법 {언어: 자바스크립트}

구현

// 최대공약수
const gcd = (n1, n2) => {
    // 일반적으로 n1이 크다고 전제하고 계산
    if (n2 > n1) {
        [n1, n2] = [n2, n1];
    };
    // n2가 0이 될 때까지 진행
    while (n2) {
        [n1, n2] = [n2, n1%n2];
    };
    return n1
};

// 단순 최소공배수
const simpleLcm = (n1, n2) => {
    for (let num = Math.max(n1, n2); num <= n1 * n2; num++) {
        if (num % n1 == 0 && num % n2 == 0) {
            return num;
        };
    };
};

// 유클리드 호제법
const uclidLcm = (n1, n2) => {
    // 최대공약수를 활용
    return (n1 * n2) / gcd(n1, n2);
};

console.log(uclidLcm(123, 456)); // 18696
console.log(simpleLcm(123, 456)); // 18696