최대공약수, 최대공배수 구하기

✅ 최대공약수(GCD, Greatest Common Divisor)

최대공약수는 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다.

const getGCD = (num1, num2) => {
    let gcd = 1;
    for(let i=2; i<=Math.min(num1, num2); i++){
        if(num1 % i === 0 && num2 % i === 0){
            gcd = i;
        }
    }
    return gcd;
}

• 2부터 시작하여 두수 중 작은 수만큼 i를 반복한다.
• num1, num2를 i로 나눈 나머지가 0일 경우 i가 gcd에 들어가고 반복한다. 
• 루프가 종료되고 최대 공약수인 gcd를 반환한다.

✅ 최소공배수(LCM, Least Common Multiple)

두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수이다.

const getLCM = (num1, num2) =>{
    let lcm = 1;
    while(true){
      if((lcm % num1 === 0) && (lcm % num2 === 0)){
        break;
      }
      lcm++;
    }
    return lcm
}

• if문 조건에 해당할 때 까지 반복한다.

✅ 유클리드 호제법

num1을 num2로 나눈 나머지를 r이라고 했을 때, gcd(num1, num2) = gcd(num2, r)과 같다. 이 말은 큰 수 2개의 gcd를 구하는 것을 축소시킬 수 있다는 것이다. gcd(num2, r) = gcd(r, r1) = ...와 같은 모습이다.

 

gcd(A, B)에서 B가 0이라면, A가 최대 공약수이다. 

 

num1 = 16, num2 = 12라고 가정하면, gcd(16,12) = gcd(4,0) 즉, gcd = 4

재귀로 해결

const getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

While로 해결

const getGCD = (num1, num2) => {
    while(num2 > 0){
        let r = num1 % num2;
        num1 = num2;
        num2 = r;
    } 
    return num1;
}

🟢 최소 공배수(LCM)

gcd를 이용하여 쉽게 구할 수 있다. 두 수 num1, num2의 최대 공약수를 gcd라고 했을 때,

최소공배수는 lcm = gcd * (num1 / gcd) * (num2 / gcd) 이다. num1 * num2 = gcd * lcm과 같다는 원리를 이용한 것이다. 간단하게 정리하면 lcm = (num1 * num2) / gcd 이다.

function solution(num1, num2) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    const lcm = (a, b) => a * b / gcd(a, b);
    return [gcd(num1, num2), lcm(num1, num2)];
}