[백준]1644_소수의 연속합

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

Solved

✔ 알고리즘 분류: 수학, 정수론, 투 포인터, 소수판정, 에라토스테네스의 채
✔ 이렇게 리뷰글을 쓰다보니 이 문제의 키포인트 알고리즘 두개가 어떻게 쓰일지 감이 오는 것 같기도??
✔ logic
1. 소수가 나왔으니 에라토스테네스의 채로 소수 그룹을 만들어주자. N은 최대 4백만까지랬으니 max는 4백만.
2. 이 소수 배열 e에서 0인 값만 투포인터를 적용해 범위의 합을 구하자. 다음 소수를 구하는 함수 next만 쓴다면 보통의 투포인터 문제가 된다.

using namespace std;
#include <iostream>
#define MAX 4000000

int n, k;
int e[MAX];
void Eratos() {
	e[1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = i * 2; j <= n; j += i) {
			if (e[j] == 1) continue;
			else e[j] = 1;
		}
	}
}

int next(int k) {
	for (int i = k + 1; i < MAX; i++)
		if (e[i] == 0) return i;
}

int main() {
	cin >> n;
	Eratos();
	int start = 2, end = 2, answer = 0;
	int sum = 0;
	while (end <= n+1) {
		if (sum >= n) {
			sum -= start;
			start = next(start);
		}
		else if (sum < n) {
			sum += end;
			end = next(end);
		}
		if (sum == n) answer++;
	}
	cout << answer << '\n';
}