[백준/BOJ] 백준 1644번 : 소수의 연속합

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

에라토스테네스의 체 알고리즘과, 투 포인터 알고리즘을 사용해서 문제를 해결했다.

 

코드

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

int n;
int primecheck[4000001];
vector<int> prime;

//에라토스테네스의 체를 이용하여 소수를 구한다
void Pre()
{
	for (int i = 0; i < 4000001; i++)
		primecheck[i] = 1;

	primecheck[0] = 0;
	primecheck[1] = 0;

	for (int i = 2; i < 4000001; i++)
	{
		if (primecheck[i] == 0)
			continue;

		prime.push_back(i);

		for (int j = i * 2; j < 4000001; j = j + i)
		{
			primecheck[j] = 0;
		}
	}
}

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

	Pre();

	cin >> n;

	//투 포인터 알고리즘을 사용하였다
	int start_pointer = 0;
	int end_pointer = 0;
	int sum = 0;
	int cnt = 0;

	while (1)
	{
		if (sum >= n)
		{
			sum -= prime[start_pointer];
			start_pointer++;
		}

		else if (prime[end_pointer] > n || end_pointer == prime.size())
		{
			break;
		}

		else if (sum < n)
		{
			sum += prime[end_pointer];
			end_pointer++;
		}

		if (sum == n)
			cnt++;
	}

	cout << cnt;

	return 0;
}