최대공약수, 최소공배수 구하기 (feat. 유클리드 호제법)

👍 최대공약수 (GCD)

Great Common Divisor

간단한 알고리즘

1. 두 숫자 n1, n2가 주어진다
2. 2부터 (n1, n2 중 작은 수)까지를 순회하며, n1과 n2 모두 0으로 나누어 떨어지는 수(gcd)를 찾아 return 한다
3. 만약 찾지 못하면, 1을 return 한다

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

👎 최소공배수 (LCM)

least common multiple

간단한 알고리즘

1. 두 숫자 n1, n2가 주어진다
2. 1부터 나눴을 때 모두 0으로 나누어 떨어지는 수(lcm)를 찾을 때까지 순회하며, 찾은 경우 return 한다

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

🤓 유클리드 호제법

기본 원리

• gcd(n1, n2) === gcd(n2, r)
  • r = n1 % n2
  • r이 0일 때 n2 값이 최대공약수이다.
• lcm = (두 자연수의 곱) / gcd

👇 예시
gcd(192,78) = gcd(78,36) = gcd(36,6) = gcd(6,0) = 6

코드

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)];
}