[Javascript] 최대공약수 구하기

// 최대공약수 구하기

function getGCD(twoNums) {
  console.log("getGCD() :: Start");
  let divisors_0 = [];
  let divisors_1 = [];
  let commonDivisors = [];
  let pnYN = [];

  // 1. 먼저 두 수가 소수인지 아닌지 판별한다.
  pnYN.push(primeNumYN(twoNums[0]), primeNumYN(twoNums[1]));

  // 2. 두 수가 소수가 아니라면
  if (
    (pnYN[0] === false && pnYN[1] === false) ||
    (pnYN[0] === false && pnYN[1] === true) ||
    (pnYN[0] === true && pnYN[1] === false)
  ) {
    // 3. 각자 나눠서 약수들을 구한다.
    divisors_0 = divisor(twoNums[0]);
    divisors_1 = divisor(twoNums[1]);

    // 4. 공약수를 구한다.
    for (let i = 0; i < divisors_0.length; i++) {
      for (let j = 0; j < divisors_1.length; j++) {
        if (divisors_0[i] === divisors_1[j]) {
          commonDivisors.push(divisors_0[i]);
          //console.log(`commonDivisors : ${commonDivisors}`);
        }
      }
    }
    // 5. 공약수들에서 최댓값을 구한다.
    return GCD(commonDivisors);
  } else {
    return 1;
  }
}

// 소수 구하는 함수 return true/false
function primeNumYN(n) {
  let result = [];

  for (let i = 1; i <= n; i++) {
    // 1부터 자기 자신까지 계속 나눠본다.
    if (n % i === 0) {
      result.push(i);
    }
  }

  let primeNumberYN = result.length > 2 ? false : true;
  return primeNumberYN;
}

// 약수 구하는 함수
function divisor(n) {
  let result = [];
  for (let i = 1; i <= n; i++) {
    if (n % i === 0) {
      result.push(i);
    }
  }
  return result;
}

// 공약수들 값에서 최댓값 구하는 함수
function GCD(arr) {
  let len = arr.length;
  let max = arr[0];

  while (len--) {
    if (arr[len] > max) {
      max = arr[len];
    }
  }
  return max;
}

/*********************
 * 함수 호출
 */

let twoNums = [71, 118];
console.time();
console.log("=========================");

let GCDresult = getGCD(twoNums);
console.log(GCDresult);

console.log("=========================");

console.timeEnd();

 

코드가 좀 길긴 하지만...

나중에 최적화해보겠음.