[백준 1644 - Node.js] 소수의 연속합

🔗 문제 링크

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

1644번: 소수의 연속합

✏️ 풀이

const N = Number(require('fs').readFileSync('/dev/stdin').toString().trim());

const isPrime = Array(N + 1).fill(true);
isPrime[0] = isPrime[1] = false;

for (let i = 2; i <= Math.sqrt(N); i++) {
  for (let j = i * i; j <= N; j += i) {
    isPrime[j] = false;
  }
}

const primes = isPrime.reduce((acc, v, i) => {
  if (v) {
    acc.push(i);
  }
  return acc;
}, []);

let sum = 0;
let count = 0;
let i = 0;
let j = 0;
while (j < primes.length) {
  sum += primes[j];
  while (sum > N) {
    sum -= primes[i];
    i++;
  }
  if (sum === N) {
    count++;
  }
  j++;
}

console.log(count);

먼저 1부터 N까지의 소수를 모두 구한 후에 투포인터를 활용하여 연속합이 N이 되는 경우의 수를 모두 세어 해결하였다.