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

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

 

문제 설명

n이 주어질 때, 연속된 소수의 합으로 n이 만들어지는 경우의 수를 찾는 문제이다.

 

주요 로직

1. 소수 찾는 로직

-> 에라토스테네스의 체를 통해 소수를 찾는다.

 

2. 투 포인터로 경우의 수 찾는 로직

-> 두개의 포인터인 i,j를 통해 합이 n이 되는 경우의 수를 찾는다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,ret;
bool che[4000004];

vector<int> era(int n){
	vector<int> v;
	for(int i=2; i<=n; i++){
		if(che[i]) continue;
		for(int j=2*i; j<=n; j += i) che[j] = 1;
	}
	
	for(int i=2; i<=n; i++)
		if(che[i] == 0) v.push_back(i);
		
	return v;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	vector<int> v = era(n);

	int i=0,j=0;
	while(i <= j && 0<=i && i<v.size() && 0<=j && j<v.size()){
		int cnt = 0;
		for(int k=i; k<=j; k++) cnt += v[k];
		if(cnt == n) i++, ret++;
		else if(cnt < n) j++;
		else if(n < cnt) i++;
	}
	
	cout << ret << "\n";
	
	return 0;
}