[300] 6388번 골드바흐의 추측

6388번 골드바흐의 추측

문제

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."을 출력한다.

예제 입력 1 복사

8
20
42
0

예제 출력 1 복사

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

try1

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
8
20
42
13
0
`
).split('\n');

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

//---- 풀이 -----//

const numberArr = [];

while (true) {
  const number = Number(input());
  if (number === 0) break;
  numberArr.push(number);
}

const isPrime = n => {
  if (n <= 1) return false;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) return false;
  }
  return true;
};

const goldbach = n => {
  for (let a = 2; a < n; a++) {
    const b = n - a;
    if (isPrime(a) && isPrime(b) && a % 2 !== 0 && b % 2 !== 0) {
      return [a, b];
    }
  }
  return [false, false];
};

const res = [];

numberArr.forEach(n => {
  const [a, b] = goldbach(n);
  res.push(a ? `${n} = ${a} + ${b}` : `Goldbach's conjecture is wrong.`);
});

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

풀이

a 는 2부터 n까지 숫자를 올려간다.

b 는 n - a로 설정한다.

a와 b 모두 소수이면서 홀수일 때 값을 리턴한다.

만약 골드바흐수가 존재하지 않으면 Goldbach's conjecture is wrong. 을 출력한다.