BOJ 1644 소수의 연속합

1 개요

BOJ 1644 소수의 연속합

• 백준 온라인 저지 1644번 문제
• BOJ 33단계

2 C++

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

int N;
int A[4000001];

int solve() {
    fill(A, A+N+1, 1);
    for(int i=2; i*i<=N; i++) {
        if(!A[i]) continue;
        for(int j=i*i; j<=N; j+=i) {
            A[j] = 0;
        }
    }
    vector<int> prime;
    for(int i=2 ; i<=N ; i++) {
        if(A[i]) {
            prime.push_back(i);
        }
    }
    int start = 0, end = 0, sum = 0, ans = 0;
    while(true) {
        if(sum > N) {
            sum -= prime[start];
            start++;
        } else {
            if(sum == N) ans++;
            if(end >= prime.size()) break;
            sum += prime[end];
            end++;
        }
    }
    return ans;
}

int main() {
    cin >> N;
    cout << solve();
}