1. 에라토스테네스의 체로, N이하의 소수를 모두 구함
2. 두 포인터로 일치하는 해당하는 연속합을 구함
초기 : start = 0, end = 1, sum = prime[0] while start < end if sum == N count++ sum -= prime[start++] //밑에서 end를 기준으로 끝을 정했으니, start를 조작한다. else if sum < N if end == numOfPrime //더이상 커질 수 없으므로 종료 break; sum += prime[end++] else sum -= prime[start++] //크므로 줄임```## 코드```cpp#include <iostream>#define MAX 4000001using namespace std;int prime[290000], tempPrime[MAX];int N, numOfPrime = 0;void generatePrime();int getResult();int main() { ios::sync_with_stdio(0); cout.tie(0); cin >> N; generatePrime(); cout << getResult();}void generatePrime() { for (int i = 2; i <= N; i++) tempPrime[i] = i; for (int i = 2; i <= N / 2; i++) { if (tempPrime[i] != -1) for (int j = 2 * i; j <= N; j += i) { tempPrime[j] = -1; } } for (int i = 2; i <= N; i++) if (tempPrime[i] != -1) prime[numOfPrime++] = tempPrime[i];}int getResult() { int start = 0, end = 1; int sum = prime[0], count = 0; while (start < end) { if (sum == N) { count++; sum -= prime[start++]; } else if (sum < N) { if (end == numOfPrime) break; sum += prime[end++]; } else sum -= prime[start++]; } return count;}