백준 1644 소수의 연속합 (C++)

1644번: 소수의 연속합

소수를 응용한 투 포인터 문제이다. 문제 자체는 간단하다. 주어진 N까지의 소수를 구한 후 투 포인터를 이용해 합이 N과 같은 경우의 수를 찾으면 된다. 문제는 평소대로 소수를 구하면 시간 초과가 나게 된다. 여기서 필요한 것은 에라토스테네스의 체이다. 이걸 사용하면 일반적으로 반복문을 돌려 비교하며 찾는 방법보다 엄청나게 빠른 속도로 찾을 수 있다. findPrime()이 이에 해당한다.
기존 방식으로 소수를 찾았다가 시간 초과로 고생을 했다. .에라토스테네스의 체 방식에 대해서는 확실히 알았으니 다음에는 잊지말고 사용하도록 하자.

#include <iostream>
#include <vector>

using namespace std;

int N, res = 0;
vector<int> v;
bool p[4000001];

void findPrime() {
    for (int i = 2; i * i <= N; i++) {
        if (p[i]) continue;
        for (int j = i + i; j <= N; j += i) {
            p[j] = true;
        }
    }

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

void findRes() {
    int sum = 0, end = 0;

    for (int i = 0; i < v.size(); i++) {
        while (sum < N && end < v.size()) {
            sum += v[end];
            end++;
        }

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

        sum -= v[i];
    }
}

void solution() {
    findPrime();
    findRes();

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    solution();

    return 0;
}