[백준] 1644번 소수의 연속합 (투포인터 알고리즘)

-문제

 

-코드

#include<stdio.h>
#include<vector>
using namespace std;

int main()
{
	int n, cnt=0, p1 = 0, p2 = 0, sum = 0;
	scanf("%d", &n);
	vector<int> a;
	vector<int> check(n+1);

	// 에라토스테네스의 체 	 	
	for (int i = 2; i*i <= n; i++)
	{
		if (check[i] == 1) continue;
		for (int j = 2 * i; j <= n; j += i)
		{
			check[j] = 1;
		}
	}

	for (int i = 2; i <= n; i++)
	{
		if (check[i] == 0)
		{
			a.push_back(i);
		}
	}

	while (1)
	{
		if (sum < n)
		{
			if (p2 >= a.size()) break;
			sum += a[p2];
			p2++;
		}
		else if(sum == n)
		{
			cnt++;
			if (p2 >= a.size()) break;
			sum += a[p2];
			p2++;
		}
		else
		{
			sum -= a[p1];
			p1++;
		}
	}
	printf("%d", cnt);
	return 0;
}