1644번 : 소수의 연속합

1. 에라토스의 체? 그걸로 일단 4000,000 까지의 소수의 집합을 구했다.

2. 2019/11/30 - [알고리즘 일기] - 2003번: 수들의 합 2 에서 사용했던 테크닉으로 값을 도출하였다.

#include<iostream>
#include<memory.h>
#include<vector>
using namespace std;

bool a[4000001];

int main() {
	memset(a, true, sizeof(a));
	int n;
	cin >> n;
	vector<int> prime;
	for (int i = 2; i < 4000001; i++) {
		if (a[i] == false) continue;
		prime.push_back(i);
		for (int j = i*2; j < 4000001; j += i) {
			a[j] = false;
		}
	}
	int R = 0;
	int L = 0;
	int ans = 0;
	int sum = prime[0];
	int p = prime.size();
	while (L <= R && R < p) {
		if (sum < n) { // 목표치보다 작음 R 증가
			R++;
			if (R >= p) break;
			sum += prime[R];
		}
		else if (sum == n) { // 같음 R 증가
			ans++;
			R++;
			if (R >= p) break;
			sum += prime[R];
		}
		else if (sum > n) { // 목표치 보다 큼 L 증가
			sum -= prime[L];
			L++;
			if (L > R&&L<p) {
				R = L;
				sum = prime[R];
			}
		}
	}
	cout << ans << '\n';
	return 0;
}