[백준] 1644 소수의 연속합 - javascript

📌 문제

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

📌 풀이

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

let n = Number(input[0]);
// 에라토스테네스의 체
let primes = [];
let check = new Array(n + 1).fill(true);
for (let i = 2; i * i <= n; i++) {
  if (!check[i]) continue;
  for (let j = i * i; j <= n; j += i) {
    check[j] = false;
  }
}
for (let i = 2; i <= n; i++) {
  if (check[i]) primes.push(i);
}

// 투포인터 탐색
let left = (sum = cnt = 0);
for (let right = 0; right < primes.length; right++) {
  sum += primes[right];
  while (sum > n) {
    sum -= primes[left];
    left++;
  }
  if (sum === n) cnt++;
}
console.log(cnt);

✔ 알고리즘 : 투포인터

✔ 에라토스테네스의 체를 이용하여 입력값 n까지의 모든 소수를 primes 배열에 저장

✔ primes 배열에서 left,right를 index 0으로 놓고 투포인터탐색 시작

✔ right를 1씩증가시켜주면서 sum값을 누적하여 n이 되는 경우의 수를 찾아야함

✔ sum이 n보다 큰 경우 n보다 작아질때까지 sum에서 left포인터값 빼주고 left포인터 1증가

❗ sum이 n보다 작은경우는 for문에서 자동으로 right포인터를 1증가시켜주기 때문에 조건문에 넣을필요 X

✔ sum이 n인 경우 cnt 1증가

✔ 난이도 : 백준 기준 골드3