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

🔗 문제 링크

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

9020번: 골드바흐의 추측

✏️ 풀이

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n')
  .map(Number);
const prime = Array(10001).fill(true);
prime[0] = false;
prime[1] = false;

for (let i = 2; i <= 100; i++) {
  for (let j = i * 2; j <= 10000; j += i) {
    prime[j] = false;
  }
}

const output = [];
for (let i = 1; i < input.length; i++) {
  const n = input[i];
  let left = right = n / 2;
  while (!prime[left] || !prime[right]) {
    left -= 1;
    right += 1;
  }
  output.push(`${left} ${right}`);
}

console.log(output.join('\n'));

먼저 10000까지의 소수를 모두 찾아낸다.

그 다음 각각의 n에 대하여 골드바흐 파티션의 좌측을 left, 우측을 right이라고 하였다.

둘 다 n / 2일 때 차이가 0으로 가장 작으므로 초기화를 n / 2로 하고, 둘 다 소수일 때까지 left는 1 감소시키고 right는 1 증가시켰다. 이렇게 하면 문제의 조건에 맞게 두 소수의 차이가 가장 작으면서 왼쪽과 오른쪽 중 왼쪽이 더 작은 골드바흐 파티션을 구할 수 있다.