백준 1644 소수의 연속합

소수 먼저 구하고 투 포인터로 해결

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);

	int n;

	cin >> n;

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

	vector<int> arr;

	for (int i = 2; i <= n; ++i)
	{
		if (nums[i])
		{
			for (int j = i * 2; j <= n; j += i)
			{
				nums[j] = false;
			}
		}
	}

	for (int i = 2; i < nums.size(); ++i)
	{
		if (nums[i]) arr.push_back(i);
	}

	int startIdx = 0;
	int endIdx = 0;

	int sum = 0;

	int answer = 0;

	while (startIdx < arr.size())
	{
		if (sum < n)
		{
			if (endIdx < arr.size())
			{
				sum += arr[endIdx];
				endIdx++;
			}
			else
			{
				break;
			}
		}
		else if (sum > n)
		{
			sum -= arr[startIdx];
			startIdx++;
		}
		else
		{
			answer++;
			if (endIdx < arr.size())
			{
				sum += arr[endIdx];
				endIdx++;
			}
			else
			{
				break;
			}
		}
	}
		
	cout << answer;

	return 0;
}