[백준 / BOJ] 17103번 골드바흐 파티션 (Javascript / Node js)

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

17103번: 골드바흐 파티션

 

문제 해석

골드바흐 파티션이란 4 -> 2 + 2 ,  8 -> 3 + 5 와 같이 소수 두개의 합으로 나타내는 표현이라고 한다.

 

10의 골드바흐 파티션은 (3 + 7), (5 + 5)이 있다.

 

(3 + 7)과 (7 + 3)은 같은 파티션으로 간주한다고 하니, 10의 골드바흐 파티션은 2개가 나오는 것을 확인할 수 있다.

 

그러니 입력 받은 짝수 N을 소수로 뺀 값이 소수가 나오는 경우의 수를 세주면 되겠다.

 

소수들의 집합은 역시 에라또스테네스의 체를 이용해 만들어주고,

(3 + 7) 과 (7 + 3)을 같은 파티션으로 간주하니, 경우의 수를 세줄 for문의 범위는 N/2까지로 잡아줘도 된다.

 

 

 

에라토스테네스의 체 관련 포스팅

[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js) (tistory.com)

[백준 / BOJ] 1929번 소수 구하기 (Javascript / Node js)

 

 

전체 코드

 

const fs = require("fs");

const input = fs

  .readFileSync("../input.txt")

  .toString()

  .trim()

  .split("\n")

  .map((item) => Number(item));

input.shift();

const Eratos = (N) => {

  let arr = Array(N + 1).fill(true);

  let cnt = 0;

  arr[0] = false;

  arr[1] = false;

  for (let i = 2; i <= Math.sqrt(N); i++) {

    for (let j = i * i; j <= N; j += i) {

      arr[j] = false;

    }

  }

  for (let i = 0; i < arr.length; i++) {

    if (arr[i]) {

      if (arr[N - i]) {

        cnt++;

      }

    }

  }

  if (arr[N / 2]) {

    return (cnt = (cnt + 1) / 2);

  } else {

    return (cnt = cnt / 2);

  }

};

let answer = [];

for (let i = 0; i < input.length; i++) {

  answer.push(Eratos(input[i]));

}

console.log(answer.join("\n"));