[C/C++] 백준 - 1644번 : 소수의 연속합

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

1644번: 소수의 연속합

에라토스테네스의 체와 투포인터를 이용해서 해결해야하는 문제이다.

소수 찾는 알고리즘은 에라토스테네스의 체가 가장 효율적이기 때문에 사용했고, 

연속 되는 부분의 합을 확인해주어야하기 때문에 투포인터를 사용했다.

 

그리고 소수 자기 자신이 연속된 수가 될 수 있기 때문에 생각을 해야할 게 2라는 소수는

연속된 수이면서 자기 자신이기 때문에 마지막에 예외처리를 해줘야 맞는다고 뜬다

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define ll long long
#define endl '\n'

using namespace std;

int N;
int Prime[4000003];

void Find_Prime(int area) {
	for (int i = 2; i <= area; i++) Prime[i] = i;
	for (int i = 2; i <= area; i++) {
		if (!Prime[i]) continue;
		for (int j = i + i; j <= area; j += i) {
			Prime[j] = 0;
		}
	}
}

int main() {
	CUNLINK;
	cin >> N;
	Find_Prime(N);
	vector<int> v;
	for (int i = 2; i <= N; i++) {
		if (!Prime[i]) continue;
		v.push_back(Prime[i]);
	}
	int Sum = 0, Cnt = 0, en = 0;
	for (int st = 0; st < v.size(); st++) {
		while (en < v.size() && Sum < N) {
			Sum += v[en];
			en++;
		}
		if (Sum == N) Cnt++;
		Sum -= v[st];
		if (en == v.size()) break;
	}
	if (N != 2 && Prime[N] != 0) Cnt += 1;
	cout << Cnt << endl;
	return 0;
}