[boj] 21919. 소수 최소 공배수 (node.js)

문제 요약

[boj] 21919. 소수 최소 공배수 (node.js)

• 주어진 숫자들 중 소수인 수들의 최소 공배수 구하기

풀이

• A * B === GCD(A, B) * LCM(A ,B) 이다.

1. 따라서 먼저 소수들을 구한 후,
2. 유클리드 호제법으로 GCD 함수를 구현하고,
3. LCM == A * B / GCD 임을 활용하여 LCM을 구했다.

• 유의: 문제 수의 범위 상 BigInt 변환해 풀이해야 한다.

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let cnt = 0;
const input = () => stdin[cnt++];

const gcd = (a, b) => {
  let x, y;
  if (a > b) {
    x = a;
    y = b;
  } else {
    x = b;
    y = a;
  }
  return x % y == 0 ? y : gcd(y, x % y);
};

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const N = input();
  const arr = input().split(" ").map(BigInt);
  let cand = [];
  let result = -1;
  arr.forEach((elem) => {
    if (isPrime(elem)) {
      cand.push(elem);
    }
  });
  if (cand.length) {
    result = cand[0];
    for (let i = 1; i < cand.length; i++) {
      result = (result * cand[i]) / gcd(result, cand[i]);
    }
  }
  console.log(result.toString());
  process.exit();
  function isPrime(num) {
    for (
      let i = BigInt(2);
      i <= BigInt(Math.trunc(Math.sqrt(Number(num))));
      i += BigInt(1)
    ) {
      if (num % i == 0) {
        return false;
      }
    }
    return true;
  }
});

주절주절

• GCD, LCM 처리 후에도 BigInt변환!!!!! 범위 확인 잊지 말자.
• 변환하면 BigInt도 for loop 가능하다!