백준 1644 소수의연속합 c++ // 소수판별 알고리즘, 투포인터

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

1644번: 소수의 연속합

1. 의사코드 및 전체코드

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/ecc7d7f58ceb4679a1bb67adbb79088c
#include <bits/stdc++.h>
using namespace std;

const int MXN = 4000002;
vector<bool> seive(MXN, true);//1.모두소수라고 가정
vector<int> primes;

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

	for (int i = 2; i * i < MXN; ++i) {
		if (!seive[i]) continue;//소수가아니면 pass
		for (int j = i * i; j < MXN; j += i)//소수들의 배수는 소수가아님
			seive[j] = false;
	}
	for (int i = 2; i < MXN; ++i) if (seive[i]) primes.push_back(i);
	primes.push_back(0); 
	// 2 3 5 7 0 일때, 끝에 0이 있어야 7을 탐색후 e가 0을 가르킴.

	int target, s = 0, e = 1, ans = 0, tmpSum = primes[0];
	cin >> target;
	while (1) {
		if (tmpSum == target) ans++;
		if (tmpSum <= target) tmpSum += primes[e++]; //end를 한칸뒤로
		if (tmpSum > target)tmpSum -= primes[s++]; //start를 한칸뒤로
		if (e == primes.size()) break;
	}
	cout << ans;

}