소수의 연속합

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

N 이상의 소수 테이블을 에라토스테네스의 체를 사용해서 구해놓고, 투 포인터를 진행하여 합을 만족하는 경우의 수를 헤아린다.

#include <iostream>
#include <vector>
#include <cstdint>

using namespace std;

uint64_t N;
vector<bool> IS_PRIME;
vector<uint64_t> PSUM;

void DoSieve(void)
{
  for (uint64_t i = 2; i * i <= N; ++i)
  {
    if (!IS_PRIME[i])
    {
      continue;
    }

    for (uint64_t j = i * i; j <= N; j += i)
    {
      IS_PRIME[j] = false;
    }
  }

  PSUM.emplace_back(0);
  for (uint64_t i = 2; i <= N; ++i)
  {
    if (IS_PRIME[i])
    {
      PSUM.emplace_back(i + PSUM.back());
    }
  }
}

uint64_t Solve(void)
{
  uint64_t ans = 0;

  uint64_t lptr = 1;
  uint64_t rptr = 1;

  while (lptr <= rptr && rptr < PSUM.size())
  {
    uint64_t sum = PSUM[rptr] - PSUM[lptr - 1];

    if (sum == N)
    {
      ++ans;
    }

    if (sum >= N)
    {
      ++lptr;
    }
    else
    {
      ++rptr;
    }
  }

  return ans;
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Input
  cin >> N;

  // Sieve
  IS_PRIME.assign(N + 1, true);
  DoSieve();

  // Solve
  cout << Solve() << '\n';

  return 0;
}