백준 소스코드 [C++] 1644 소수의 연속합

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

백준 소스코드 [C++] 1644 소수의 연속합

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;
bool notSosu[4000001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 2;i <= sqrt(4000000);i++) {
		if (notSosu[i] == false) {
			for (int j = i * i;j <= 4000000;j = j +i)
				notSosu[j] = true;
		}
	}

	vector<int> prime;
	for (int i = 2; i < 4000000; i++) {
		if (notSosu[i] == false)
			prime.push_back(i);
	}

	int l = 0, r = 0,sum=0,cnt=0;
	while (true) {
		if (sum >= n) sum -= prime[l++];
		else if (r == prime.size()) break;
		else sum += prime[r++];
		
		if (sum == n) cnt++;
	}
	cout << cnt;

	return 0;
}