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

증가되는 소수의 값들을 기준으로 투포인트를 활용해서 푸는 문제이다.  

 

에라토네스의 체를 활용하여 N값까지의 소수들을 벡터에 넣어주고 

시작 포인터와 끝 포인터를 지정해서 sum값을 갱신해나간다. 

 

while문에서 조건이 총 4개이다. 

 

첫번째, sum 값이 n보다 크거나 같으면 시작 포인트를 하나 올려준다. 

두번째, 끝 포인트가 벡터의 사이즈까지 도달했으면 break 해준다. 

세번째, sum 값이 n보다 작으면 끝 포인트를 증가시켜준다. 

네번째, sum과 n 이 같으면 카운팅 해준다. 

 

시작포인트와 끝포인트는 0번째 인덱스를 시작으로 while문이 시작된다. 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
vector<bool> check;
int main() {
	vector <int> v;
	int n; cin >> n;
	check.resize(n + 1, 0);
	for (int i = 2; i <= n; i++) {
		if (check[i])continue;
		else {
			v.push_back(i);
			for (int j = i * 2; j <= n; j += i)check[j] = 1;
		}
	}
	int s, e, sum, cnt;
	s = e = sum = cnt = 0;
	while (1) {
		if (sum >= n)sum -= v[s++];
		else if (e == v.size())break;
		else sum += v[e++];
		if (sum == n)cnt++;
	}
	cout << cnt;

}

1644번: 소수의 연속합