백준 1644번 소수의 연속합

에라토스테네스의 체로 4000000 이하의 소수를 구하고 투포인터의 기본적인 방식(합이 n보다 작을경우 b를 늘리고 클경우 a를 늘린다)을 반복하여 조건을 만족할 경우를 카운트하여 출력한다.

#include <iostream>
#include <vector>

using namespace std;

int N;
int arr[4000001];
vector <int> prime;

int main() {
	cin >> N;

	for (int i = 2; i <= 4000001; i++)
	{
		if (arr[i] == 0) {
			prime.push_back(i);
			for (int j = 2; i*j <= 4000001; j++)
			{
				if (arr[i * j] == 0) {
					arr[i * j] = 1;
				}
			}
		}
	}

	int a=0, b=0;
	int total = 2;
	int cnt = 0;
	while (b < prime.size()-1) {
		if (total == N) {
			cnt++;
			b++;
			total += prime[b] - prime[a];
			a++;
		}
		else if (total < N) {
			b++;
			total += prime[b];
		}
		else {
			total -= prime[a];
			a++;
		}
	}
	
	cout << cnt;

	return 0;
}