9020 - 골드바흐의 추측 - node.js

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

9020번: 골드바흐의 추측

---

2보다 큰 모든 짝수는 두 소수의 합이라는 골드바흐의 추측, 이러한 골드바흐의 추측을 해결하는 문제로, 2보다 큰 짝수가 주어졌을 때 골드바흐 파티션. 즉, 두 소수를 출력하면 되는 문제다.

1. 2보다 큰 짝수가 주어지면

2. 골드바흐 파티션(그 수를 이루는 두 소수)을 출력해라

3. 만약 골드바흐 파티션이 여러개라면, 두 소수의 차이가 가장 적은 것을 출력해라

 

예를 들어 골드바흐 파티션이 두 개 이상인 경우. 10이라고 한다면 [3, 7], [5, 5]이 있을 텐데 3, 7보다 5, 5가 두 수의 차가 적으므로 5, 5를 출력해야 한다.

제한된 입력값의 범위가 4 <= n <= 10,000이므로 소수를 이전에 사용했던 방법을 통해 10,000까지 찾아서 배열에 저장해둬도 좋다.

 

주어진 수에서 소수를 빼고 그 답이 소수라면 출력하는 방법?

= 직관적으로 해결 가능한 방법이지만, 위의 상황처럼 골드바흐 파티션이 여러개일 경우 즉 10의 경우는 5, 5가 아닌 3, 7이 출력될 것이다.

 

배열에 골드바흐 파티션을 모두 저장한 뒤 걸러내는 방법?

= 주어진 수에서 소수를 차례로 계산해서 골드바흐 파티션을 만들고 만들어진 골드바흐 파티션을 모두 배열에 저장한다. 이대로 주어진 수까지 계속 계산을 반복한다면 10의 예를 들어보자면 [3, 7] [5, 5] [7, 3]이 들어갈 것이므로 계산할 소수는 주어진 수의 1/2만큼까지만 계산하게 하면 반복 없이 계산될 것이다. 그리고 가장 마지막에 들어온 골드바흐 파티션을 출력하면 된다.

 

주어진 수 / 2가 둘인 경우에 가깝게 찾는 방법?

= 주어진 수의 / 2가 둘일 때 가장 가까운 소수가 나온다. 10이라면 5, 5의 예로 알 수 있다. 우선 이전에 사용했던 에라토스테네스의 체를 사용해서 배열에 4 <= n <= 10,000의 소수를 담아둔다. 골드바흐 파티션을 둘로 구분하고(왼쪽 오른쪽 or 첫번째 두번째 or A B) 주어진 수의 n/2부터 시작해서 A는 1씩 줄여가고 B는 1씩 늘려간다. 둘 모두 소수라면 반복문을 멈춘뒤 해당 값을 출력하면 된다.

 

// 입력값 가져오기, 공백 제거와 숫자로 변환, 줄넘김 기준으로 input에 넣기
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n").map(Number);

// 에라토스테네스의 체로 소수 찾기
const primes = Array(10001).fill(true);
primes[0] = false;
primes[1] = false;
for (let i = 2; i <= 100; i++) {
  for (let j = i * 2; j <= 10000; j += i) {
    primes[j] = false;
  }
}

// 출력할 결과 result 할당. 골드바흐 파티션 A, B에 입력값 /2 각각 넣기
const result = [];
for (let i = 1; i < input.length; i++) {
  const n = input[i];
  let A = n / 2;
  let B = n / 2;
  // 입력값 /2부터 시작해서 둘 다 소수가 아닌 경우 A는 -1, B는 +1하면서 소수가 될때까지 반복.
  while (!primes[A] || !primes[B]) {
    A -= 1;
    B += 1;
  }
  // 반복문이 멈췄을 때 즉, A,B가 소수일 때 그 값을 result에 추가해두기
  result.push(`${A} ${B}`);
}
//위 코드를 마치고 난 뒤 최종 결과를 result에 줄넘김을 추가해서 출력하기
console.log(result.join("\n"));