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

✍️ 첫번째 접근

문제를 해결하기 위해서 해당 범위까지의 소수가 무엇이 있는지 알아야 한다고 생각했다. 소수를 구하는데 효과적인 에라토스테네스의 체를 사용해 문제에서의 최대 범위까지의 소수를 먼저 구했다.
그 후, 가장 작은 소수에서부터 입력받은 N까지 반복문을 도는데 2개의 포인터를 사용하여 돌면 된다. 연속된 소수의 합을 구할 수 있으면 cnt를 하나 증가하여 문제를 해결할 수 있다.

#include <bits/stdc++.h>
#define MAX 4000002
using namespace std;
bool arr[MAX];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    fill(arr,arr+MAX,true);
    arr[1] = false;
    for(int i = 2; i <= MAX; i++) {
        if(arr[i] == true) {
            for(int j = i+i; j <= MAX; j+=i) {
                arr[j] = false;
            }
        }
    }

    int n;
    cin >> n;

    int en = 2;
    int cnt = 0;
    for(int st = 2; st <= n;st++) {
        int sum = 0;
        en = st;
        if(!arr[en])
        continue;
        while(sum <= n && en <= n) {
            if(arr[en]) {
                sum += en;
            }
            if(arr[en] && sum == n) {
                ++cnt;
                break;
            }
            ++en;
        }
    }
    cout << cnt;

    return 0;
}```