[백준 1644] 소수의 연속합 (C++)

문제 링크: https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

1. 주의할 점

- 에라토스테네스의 체를 이용하여 소수들을 구한다

- N=1일때 0을 출력한다

- 투 포인터를 이용하여 해결한다

 

2. 구현

- 에라토스테네스의 체를 이용하여 구한 소수들을 벡터에 담는다

- 투포인터를 통해 구간의 합이 Num과 같은지 확인한다

- 구간의 합(Sum)이 Num보다 작을 때, 같을 때, 클 때 모두 조건을 통해 해결한다

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
int primary[4000001], num;

void cal() {
	for (int i = 2; i <= num; i++)
		primary[i] = i;
	for (int i = 2; i <= sqrt(num); i++) {
		if (primary[i] == 0) continue;
		for (int j = i + i; j <= num; j += i)
			primary[j] = 0;
	}
}

int main() {
	cin >> num;
	if (num < 2)
		cout << 0 << '\n';
	else {
		cal();
		vector<int> v;
		for (int i = 2; i <= num; i++)
			if (primary[i])
				v.push_back(i);
		int r = 0, l = 0, cnt = 0;

		int sum = v[0];
		while (l <= r && r != v.size()) {
			if (sum == num) {
				cnt++;
				if (l == r) {
					r++;
					if (r == v.size()) break;
					sum += v[r];
				}
				else {
					sum -= v[l];
					l++;
				}
			}
			else if (sum > num) {
				if (l == r) break;
				else {
					sum -= v[l];
					l++;
				}
			}
			else if (sum < num) {
				r++;
				if (r == v.size()) break;
				sum += v[r];
			}
		}
		cout << cnt;
	}
	system("pause");
	return 0;
}