[JavaScript] 최대공약수(GCD) & 최소공배수(LCM) 구하기

최대공약수(Greatest Common Divisor)

최대공약수는 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다. 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법이다.

let 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;
}

 

최소공배수(Lowest Common Multiple)

최소공배수는 두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수이다. 최소공배수는 1부터 시작하여 점차 +1을 하면서 각각의 두 수를 최소공배수로 나누었을 때 나머지 값이 0인지를 비교한다.

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

 

유클리드 호제법을 이용한 구현

유클리드 호제법의 기본 원리는 num1을 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것이다. r이 0이라면, 그때의 num2가 최대공약수이다.

num1 = 24, num2 = 16 이라고 가정하면 GCD(24, 16) = GCD(16, 8) = GCD(8, 0), 즉 최대공약수는 8이다. 

여기서 num1 < num2 의 경우 값이 자동 스왑된다. 예를 들어 num1 = 16, num2 = 24 의 경우 getGCD(24,(16%24 = 16))이 불러지게 된다. 재귀로 접근하지 않는다면 아래와 같이 구현된다.

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

• 최소공배수는 위에서 구했던 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)];
}