[BOJ] 1644

참고자료와 강의를 들으니 바로 풀리는 문제였다. 

에라토스테네스의 체로 소수를 모두 구한 뒤 two pointer를 사용해 구하면 되는 문제였다. 

MAX 값을 4000000으로 고정 시킨 후 4000000까지의 소수를 구한 후 해당 소수들을 vector에 저장시켰다.

그 후 vector안의 값의 합이 입력 값과 같은지 two pointer를 사용해 확인한다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 4000000;
 
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); 
    vector<int> prime;
    bool isPrime[MAX+1];
    fill(isPrime+2, isPrime+MAX+1, true);
    for(int i=2; i<=MAX; i++){
        if(isPrime[i]) prime.push_back(i);
        for(int j=i*2; j<=MAX; j+=i)
            isPrime[j] = false;
    }
    
    int N,M,result = 0, sum = 0, lo = 0, hi = 0;
    cin >> M;
    N = prime.size();
    while(1){
        if(sum >= M) sum -= prime[lo++];
        else if(hi == N) break;
        else sum += prime[hi++];
        if(sum == M) result++;
    }
    cout << result << "\n";
}