백준17103 - 골드바흐 파티션 node.js

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

 

문제 해결 방식

수의 범위가 100만 이하이기 때문에,

- 에라스토테네스의 체를 활용하여 모든 소수를 탐색하고

- 테스트케이스에 따라 조건에 맞는 파티션을 찾아내는 방식으로 접근했다.

 

에라스토테네스의 체는 다음과 같은 로직으로 생성하였다.

function makingPrimes(n) {
  // 소수를 판정하기 위한 배열
  const primes = Array.from({ length: n + 1 }, () => true);
  (primes[0] = false), (primes[1] = false);

  for (let i = 2; i <= n; i++) {
    if (primes[i]) {
      let j = 2;
      while (i * j <= n) {
        primes[i * j] = false;
        j++;
      }
    }
  }

  return primes;
}

 

골드바흐 파티션을 찾는 로직은 다음과 같다.

function act(x, primes) {
  let cnt = 0;
  for (let i = 1; i <= Math.floor(x / 2); i++) {
    if (primes[i] && primes[x - i]) cnt++;
  }

  return cnt;
}

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  data.shift();
  const arr = data.map(Number);
  const max = Math.max(...arr);
  const primes = makingPrimes(max);

  const result = arr.map((el) => act(el, primes));
  console.log(result.join("\n"));
}

function makingPrimes(n) {
  const primes = Array.from({ length: n + 1 }, () => true);
  (primes[0] = false), (primes[1] = false);

  for (let i = 2; i <= n; i++) {
    if (primes[i]) {
      let j = 2;
      while (i * j <= n) {
        primes[i * j] = false;
        j++;
      }
    }
  }

  return primes;
}

function act(x, primes) {
  let cnt = 0;
  for (let i = 1; i <= Math.floor(x / 2); i++) {
    if (primes[i] && primes[x - i]) cnt++;
  }

  return cnt;
}

solution(input);