BOJ 1644 : 소수의 연속합

풀이요약

에라토스테네스의 체, 투 포인터

풀이상세

1. $N$ 까지의 연속되는 소수를 구한다.

2. 투포인터를 통해, 값이 큰 경우는 앞의 인덱스를 빼서 감소시키고, 값이 작은 경우는 다음 인덱스를 넣어, 연속합을 늘려간다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int N, ans, sum, l, r;
vector<int> pv;
bool visited[4000000 + 4];

void input() {
    cin >> N;
}

// N까지의 소수를 구함
void goPrimeNums() {
    for (int i = 2; i <= sqrt(N); i++) {
        if (!visited[i]) for (int j = i + i; j <= N; j += i) visited[j] = true;
    }

    for (int i = 2; i <= N; i++) {
        if(!visited[i]) pv.push_back(i);
    }
}

void findN() {
    int sum = 0, l = 0, r = 0;
    while (true) {
        if (sum >= N) sum -= pv[l++];
        else if(r >= pv.size()) break;
        else sum += pv[r++];
        if (sum == N) ans++;
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    goPrimeNums();
    findN();
    output();
}