[백준 1644] 소수의 연속합

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

소수를 구하고 누적합과 투포인터를 사용하면 쉽게 풀 수 있는 문제이다.
소수를 효과적으로 구하는 방법을 찾아 보니 에라토스테네스의 체라는 방법이 있었다.

풀이 과정

1. 에라토스테네스의 체를 활용해 소수를 구한다.
2. n까지의 소수들을 누적합 한다.
3. 투포인터를 사용하여 구간합을 구한다.(끝 값의 누적합 - 시작 값의 누적합)
   • 끝 값을 증가시키면 값이 커지고, 시작 값을 증가시키면 값이 작아진다.
4. 구간 합을 n과 비교한다.
   • n과 같으면 cnt++ 하고 끝 값을 증가 시킨다.
   • 누적 합이 n보다 크다면 시작 값을 증가 시킨다.
   • 누적 합이 n보다 작으면 끝 값을 증가 시킨다.
5. 끝 값이 소수들의 개수보다 커지면 종료한다.

구현

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n <= 1) {
        cout << 0;
        return 0;
    }

    vector<bool> Pri(n + 1, true); 
    Pri[0] = Pri[1] = false; 

    for (int i = 2; i * i <= n; i++) {
        if (Pri[i]) {
            for (int j = i * i; j <= n; j += i) {
                Pri[j] = false;
            }
        }
    }

    vector<int> sums;
    sums.push_back(0); 

    for (int i = 2; i <= n; i++) {
        if (Pri[i]) {
            sums.push_back(sums.back() + i);
        }
    }

    int s = 0, e = 0;
    int cnt = 0;

    while (e < sums.size()) {
        int sum = sums[e] - sums[s];

        if (sum == n) {
            cnt++;
            e++;
        } else if (sum < n) {
            e++;
        } else {
            s++;
        }
    }

    cout << cnt;
    return 0;
}