[C++] 백준 1644번: 소수의 연속합

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

1644번: 소수의 연속합

에라토스테네스의 체와 두 포인터를 활용하여 풀 수 있는 문제다. N까지의 소수 리스트를 구하는데 시간이 상대적으로 더 오래 걸린다. 처음 제출에서 시간초과가 나서 두 번째 제출에서는 sqrt, vector::size 중복 연산을 없애고 그 외 자잘한 산술연산도 줄였더니 AC를 받을 수 있었다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>
#define VB vector<bool>
#define VVB vector<VB>


int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N;
	cin >> N;

	VI primeNumbers;
	VB sieve(N + 1, true);
	primeNumbers.push_back(2);
	for (int num = 3; num <= N; num += 2) {
		if (sieve[num] == false)
			continue;
		bool isPrime = true;
		double divLimit = sqrt(num);
		for (int div = 2; div <= divLimit; ++div) {
			if (num % div == 0) {
				isPrime = false;
				break;
			}
		}
		if (isPrime) {
			primeNumbers.push_back(num);
			for (int product = num * 2; product <= N; product += num)
				sieve[product] = false;
		}
	}

	int ans = 0, i = 0;
	const int primeSize = primeNumbers.size();
	while (i < primeSize) {
		int j = i + 1, sum = primeNumbers[i];
		while (j < primeSize && sum < N)
			sum += primeNumbers[j++];
		if (sum == N) ans++;
		++i;
	}

	cout << ans << EL;

	return 0;
}