문제 간략 설명

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수가 있다. 자연수 N이 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

풀이 방법

에라토스테네스의 체로 N까지의 소수를 생성한다. 투포인터로 합이 N인 부분합을 탐색한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> primes;

void get_prime(int n) {
	vector<bool> is_prime(n + 1, true);

	is_prime[0] = false;
	is_prime[1] = false;

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

	for (int i = 2; i <= n; i++)
		if (is_prime[i])
			primes.push_back(i);
}

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

	cin >> N;

	get_prime(N);

	int left = 0, right = 0;
	int sum = 0;
	int res = 0;

	while (true) {
		if (sum == N)
			res++;
		if (sum >= N) {
			sum -= primes[left];
			left++;
		} else {
			if (right == primes.size())
				break;
			sum += primes[right];
			right++;
		}
	}

	cout << res << endl;

	return 0;
}

Key Points