[백준 #1644] 소수의 연속합, 자바스크립트 풀이

문제 난이도	유형
🥇골드 3티어	소수판별, 에라토스테네스의 체, 투 포인터 알고리즘

 

문제

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	29230	12431	8657	41.498%

 

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

 

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

예제 입력

41

 

예제 출력

3

---

풀이

자연수 N이 주어졌을 때, 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야 한다. "연속된" , "경우의 수", "소수의 합(부분합)" 이란 키워드를 보고 투 포인터를 통해 해결할 수 있음을 알 수 있었다. 투 포인터 알고리즘을 사용하기 위해서는 1차원 배열이 있어야 하는데 이곳에서 "소수의 합" 이 부분합이라 가정한다면 우리는 특정 범위의 소수 배열을 가지고 시작해야 함을 알 수 있다. 유의해야 할 것은 소수의 범위인데 만약 위의 예제 입력처럼 N이 41인 경우에는 41 자체로도 부분합이 되기 때문에 소수 배열의 범위는 N까지 임을 알 수 있다. 

 

우리가 필요한 소수 배열을 구하기 위해서 아래 이미지가 설명하는 에라토스테네스의 체 알고리즘을 사용해 O(n log log n) 의 시간 복잡도로 N까지의 소수 배열을 만들어낼 수 있다. 이처럼 다수의 소수를 빠르게 찾아야 하는 문제에서는 에라토스테네스의 체 알고리즘을 사용하면 적절하다.

 

출처: https://en.wikipedia.org/wiki/Eratosthenes#Number_theory

 

에라토스테네스의 체 알고리즘을 통해서 소수 배열을 구한 이후 투 포인터 알고리즘을 이용해 경우의 수를 구할 수 있다.

 

코드

let input = [];
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", function (line) {
  input = Number(line.trim());
}).on("close", function () {
  solution(input);
  process.exit();
});

function get_primes(num) {
  let arr = Array(num + 1)
    .fill(true)
    .fill(false, 0, 2);
  for (let i = 2; i * i <= num; i++) {
    if (arr[i]) {
      for (let j = i * i; j <= num; j += i) {
        arr[j] = false;
      }
    }
  }
  return arr;
}

function solution(N) {
  const primes = get_primes(N)
    .map((v, i) => (v ? i : 0))
    .filter((e) => e);
  let start = 0;
  let end = 0;
  let partialSum = primes[0];
  let count = 0;
  while (start < N && end < N) {
    if (partialSum === N) count++;
    if (partialSum > N) {
      partialSum -= primes[start];
      start += 1;
    } else {
      end += 1;
      partialSum += primes[end];
    }
  }
  console.log(count);
}