1. 최대공약수(GCD)

---

• 공약수(common divisor)란 두 수 이상의 여러 수의 공통된 약수를 의미하며, 최대공약수(Greatest Common Divisor, GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 말한다.

• 최대공약수를 담을 변수에 초기값을 1로 주고(1은 모든 수들의 공약수), i를 1부터 두 수 중 작은 수까지 1씩 증가시키면서 num1과 num2 모두 0으로 나누어 떨어지는 i를 구한다.

• 이때 if문 안의 GCD = i에 return문이 붙어있지 않으므로 1이 들어가면 바로 조건을 만족하지만 들어간다고 바로 함수가 종료되지 않는다. i에 1이 들어가면 if문의 조건을 반복문이 시작하자마자 바로 만족한다. 하지만 GCD = i에 return문이 붙어있지 않으므로 i는 num까지 계속 반복문을 그대로 진행한다.

• 그래서 최종적으로 GCD에는 조건을 만족하는 i(두 수의 공약수 들)들 중 가장 마지막으로 들어간 수(최대 공약수)가 담기게 된다.

function greatestCommonDivisor (num1, num2) {
  let GCD = 1;

  // num1과 num2중 작은 수를 기준으로 하는 이유는 두 개의 수가 공통적으로 가지고 있는 공약수 이어야 하므로 최대 공약수는 두 개의 수보다 큰 값이 나올 수 없다.
  for (let i = 1; i <= Math.min(num1, num2); i++) {
    if (num1 % i === 0 && num2 % i === 0) {
      GCD = i;
    }
  }
  return GCD;
};

1) 유클리드 호제법

• 2개의 자연수 a와 b가 있을 때, num1을 num2로 나눈 나머지를 rest이라 하면, num1과 num2의 최대공약수는 num2와 rest의 최대공약수와 같다.

• 이러한 성질에 따라 num2를 rest로 나눈 나머지 rest’를 구하고, 다시 rest을 rest’로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 num1과 num2의 최대공약수가 된다.

function gcd(num1, num2) { // 단, num1이 num2보다 커야함.
    while ((num1 % num2) > 0) {
        let rest = num1 % num2;
        num1 = num2;
        num2 = rest;
    }
    return num2;
}

2. 최소공배수(LCM)

---

• 공배수(common multiple)란 두 수 이상의 여러 수의 공통된 배수를 의미하며, 최소공배수(Lowest Common Multiple, LCM)란 두 수 이상의 여러 수의 공배수 중 최소인 수를 말한다.

• 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나눠주면 구할 수 있다.

function lowestCommonMultiple (num1, num2) {
  return num1 * num2 / 'num1과 num2의 최대공약수'
};