[백준] 17103 골드바흐 파티션 (소수)

백준 단계별로 풀어보기에서 소수 관련 문제들을 풀었다.
소수를 구하는 방법은 다양하지만 그 중에서 가장 빠른 알고리즘인 에라토네스 체에 대해서 공부했다.

먼저, 소수란 1과 자기 자신을 제외한 수로는 나누어 떨어지지 않는 수를 말한다.
에라토네스 체의 원리는 어떤 수의 배수는 소수가 아니라는 점을 이용한다.
2의 배수인 4,6,8,10...을 목표 숫자까지 제거하고, 3의 배수인 3,6,9,12...을 목표 숫자까지 제거한다. 중복된 숫자를 제외하고 반복적으로 숫자를 제거하면 소수만 남게 된다. 이 소수만 남게된 체?를 이용해서 소수 배열을 생성할 수도 있고 소수 관련 문제를 응용해서 해결할 수 도 있다.

17103 골드바흐 파티션

문제해결에 굉장히 오랜 시간이 걸렸다. 에라토네스 체를 이용해서 소수 배열을 생성한 숫자 2개를 뽑아서 짝수를 만드는 식으로 문제를 해결하려고 했었는데 시간 초과가 발생했다. 그래서 소수 배열을 만들지 않고 에라토네스 체만 이용해서 반복문을 통해서 문제를 해결했다.

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [T, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n").map(Number);

const max = Math.max(...arr);
const obj = { 1: true };
for (let i = 2; i <= Math.sqrt(max); i++) {
  if (obj[i]) {
    continue;
  }
  for (let j = i ** 2; j <= max; j += i) {
    obj[j] = true;
  }
}

const answer = [];
for (let N of arr) {
  let temp = 0;
  for (let i = 1; i <= Math.floor(N / 2); i++) {
    if (!obj[i] && !obj[N - i]) {
      temp++;
    }
  }
  answer.push(temp);
}
console.log(answer.join("\n"));

출처
골드바흐 파티션: https://www.acmicpc.net/problem/17103