[boj] 6588. 골드바흐의 추측 (node.js)

문제

[boj] 6588. 골드바흐의 추측 (node.js)

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

• 위의 골드바흐의 추측에 대해, 짝수가 주어질 때 골드바흐의 추측을 검증하는 문제

풀이

• 에라토스테네스의 체를 먼저 구현하여 0, 1로 소수 여부를 판별하여 배열에 담아 두었다.
• 문제에서 원하는 결과가 답이 여러 개일 경우 두 홀수의 차가 가장 큰 경우를 출력하는 것이므로,
• 탐색 함수를 통해 (주어진 짝수 - 1) 부터 -2씩 이동하며 그 값과 그 값과 짝이 되는 수의 소수 여부를 확인한다.

생각

• 처음에 그럴 필요 없는 문제를 또 이분탐색 쓴다고 삽질했다. 인덱스로 접근하여 그 값을 확인할 때는, 배열의 값으로 접근할 때보다 훨씬 간단하게 풀리는 경우가 많다. 배열의 인덱스를 이용하는 건 오히려 두 번 꼬인 문제라는 걸 인식하고 제대로 풀자!

전체 풀이

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

// 에라토스테네스의 체
let isPrime = new Array(1000000 + 1).fill(1);
isPrime[1] = 0;
for (let i = 2; i <= 1000000; i++) {
  for (let j = 2; i * j <= 1000000; j++) {
    if (isPrime[i * j] == 0) continue;
    isPrime[i * j] = 0;
  }
}

const solution = () => {
  let results = [];
  while (1) {
    let n = Number(input());
    if (n == 0) break;
    let result = search(2, n - 1, n);
    results.push(`${n} = ${n - result} + ${result}`);
  }
  console.log(results.join("\n"));
};

function search(L, R, n) {
  while (L <= R) {
    let L = n - R;
    if (isPrime[L] && isPrime[R]) {
      return R;
    } else R -= 2;
  }
}

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

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});