[백준 6588 - Node.js] 골드바흐의 추측

🔗 문제 링크

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

✏️ 풀이

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(Number);

const primeNums = [];
const nums = Array(1_000_000 + 1).fill(true);
nums[0] = false;
nums[1] = false;

for (let i = 2; i <= Math.sqrt(1_000_000); i++) {
  if (!nums[i]) {
    continue;
  }
  primeNums.push(i);
  for (let j = i * 2; j <= 1_000_000; j += i) {
    nums[j] = false;
  }
}

console.log(
  input.slice(0, -1).map(num => {
    const low = primeNums.find(primeNum => nums[num - primeNum]);
    if (low) {
      const high = num - low;
      return `${num} = ${low} + ${high}`;
    }
    return "Goldbach's conjecture is wrong.";
  }).join('\n')
);

먼저 1,000,000까지의 자연수 중에서 소수를 모두 구한다. 그 다음 주어진 수들을 가장 작은 소수부터 큰 소수까지 순서대로 두 값의 차가 소수가 되는 가장 작은 소수를 찾는다. 그러한 소수가 존재하면 n = a + b 형태로 출력하고, 존재하지 않으면 골드바흐의 추측이 틀렸다는 문자열을 반환하면 된다.