소수를 판별하는 부분이 중요한 문제이다.

소수란 (prime number) 1~n 까지 숫자중에서
1과 n을 뺀 나머지 숫자로 나눠지지 않는 숫자이다.

이것을 단순하게 for문으로 구현하면 50점짜리 답.
-> 시간초과가 발생한다.

여기서 한시간을 싸매다가 풀이를 참고하게 되었다.

풀이

소수를 판별하는 법을 신기하게 풀어내는데

에라토스테네스의 체 라는 소수 판별법이 있다.
원리는 간단하다


(1은 소수가 아니다.)

1. 2의 배수는 2가 약수이므로 소수가 아니다.
2. 3의 배수는 3이 약수이므로 소수가 아니다.
3. 4는 이미 소수가 아니다.
4. 5의 배수는 5가 약수이므로 소수가 아니다.

이런식으로 쭉쭉 나가면 소수만 남게 된다.

이렇게 소수를 판별 한 소수들을 벡터에 넣어준다.

그리고 두개의 포인터로 다루면 금방 해결 가능.

소수들을 벡터에 넣어서 다루기 쉽게 만드는것이 중요하다.
(소수와 소수가 아닌수가 섞인 배열에서 포인터를 움직이려니 너무 복잡해짐)

코드

#include <bits/stdc++.h>

using namespace std;

int n;
int arr[4000001];
vector<int> v;


// 에라토스테네스의 체
/**
* 2는 소수이다. 그러면 2의 배수들은 전부 소수가 아니다
* 3은 소수이다. 그러면 3의 배수들은 전부 소수가 아니다
* ...
* 소수가 아닌 수만 남게됨.
*/

void chae(int n)
{
	fill(arr, arr + 4000001, 1);

	arr[1] = 0;

	for (int i = 2; i <= n; i++)
	{
		if (arr[i] == 1) // 해당 수가 소수라면
		{
			v.push_back(i);
			for (int j = i * 2; j <= n; j += i) // 해당 수의 배수들은 전부 소수가 아님
			{
				arr[j] = 0;
			}
		}
	}
}

int main()
{
	cin >> n;

	chae(n);

	int st = 0;
	int en = 0;
	int sum = 0;
	int result = 0;

	while (1)
	{
		if (sum > n)
		{
			sum -= v[st++];
		}
		else if (sum < n)
		{
			if (en >= v.size())
				break;

			sum += v[en++];
		}
		else
		{
			result++;

			if (en >= v.size())
				break;

			sum += v[en];
			en++;
		}
	}

	cout << result;

	return 0;
}