[BJ 1644] 소수의 연속합

풀이방법 : 에라스토테네스의 체 + 투 포인터

해결 : 에라스토테네스의 체를 구현 하여 2부터 N(포함) 까지 모든 수에 대해서 소수를 판별하여

새로운 수열을 만들어 투포인터로 O(n) 시간 복잡도로 해결.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

bool isP(int input) {
	for (int i = 2; i <= input / 2; i++) {
		if (input % i == 0) {
			return false;
		}
	}
	return true;
}

void setPri(vector<bool>& isPrime) {
	for (long long int i = 2; i * i <= isPrime.size(); i++) {
		if (isP(i)) {
			isPrime[i] = true;
			int t = 2;
			while (true) {
				int idx = i * t;
				if (idx > isPrime.size() - 1) {
					break;
				}
				isPrime[idx] = false;
				t++;
			}
		}
	}
}

int main(void) {
	//입출력 속도
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	if (n == 1) {
		cout << 0;
		return 0;
	}

	vector<bool> isPrime(n + 1,true);

	setPri(isPrime);

	vector<int> v;
	for (int i = 2; i < isPrime.size(); i++) {
		if (isPrime[i]) {
			v.push_back(i);
		}
	}

	int s = 0;
	int e = 0;
	long long int sum = v[s];
	int ret = 0;
	while (true) {
		if (sum < n) {
			e++;
			if (e == v.size()) {
				break;
			}
			sum += v[e];
		}
		else if (sum > n) {
			sum -= v[s];
			s++;
		}
		else {
			ret++;
			s++;
			e = s;
			if (e == v.size()) {
				break;
			}
			sum = v[e];			
			//같은 케이스.
		}
	}

	cout << ret;

	return 0;
}