[BJ / 6588] 골드바흐의 추측

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

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

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.
이 추측은 아직도 해결되지 않은 문제이다.
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예시

풀이

처음에 풀이를 했을 때는 시간초과로 문제를 해결하지 못했었다.
입력된 수까지의 소수를 매번 모두 구하고, 가장 작은 수를 구하려고 했기 때문인 것 같았다.
그래서 가장 큰 수인 1000000까지의 수 중 소수가 아닌 수와 짝수를 제외한 배열을 만들고, 그 중 가장 작은 수를 찾아서 있다면 출력하도록 구현하였다.

const readline = require('readline');

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

let input = [];
rl.on('line', (line) => {
  input.push(parseInt(line));
});

rl.on('close', () => {
  console.log(solution(input));
});

function solution(num_array) {
  const nums = Array(1000000 + 1).fill(true);
  nums[0] = false;
  nums[1] = false;
  let guess = [];
  let answer = '';
  for (let i = 2; i <= Math.sqrt(1000000); i++) {
    if (!nums[i]) continue;
    guess.push(i);

    for (let j = i * 2; j <= 1000000; j += i) {
      nums[j] = false;
    }
  }
  num_array.map((v, i) => {
    const minimum = guess.find((num) => nums[v - num]);

    if (v > 1) {
      if (minimum) {
        const maximum = v - minimum;
        answer += `${v} = ${minimum} + ${maximum}`;
      } else answer += `Goldbach's conjecture is wrong.`;
    }

    if (i !== num_array.length - 1) {
      answer += '\n';
    }
  });
  return answer;
}