[C/C++ 백준 1644번] 소수의 연속합 (Gold 3)

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

에라토스테네스의 체와 투 포인터를 이용하는 문제.

 

체를 만들어 놓고 N까지 벡터에 넣어놓은 뒤, 투 포인터로 연속합을 체크해주면 된다. 계속 98%에서 런타임 에러가 났었는데,, 1일때의 처리를 꼭 해주자.

 

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
vector <int> Prime;
bool chae[4000001];
int main(void){
	fill(chae, chae+4000001, false);
	for(int i=2; i<4000001; i++){
		if(!chae[i]){
			for(int j = i+i; j<4000001; j+=i){
				if(!chae[j])
					chae[j] = true;
			}
		}
	}
	int N;
	scanf("%d", &N);
	if(N==1)
		printf("0");
	else{
	if(N>=2)
		Prime.push_back(2);
	for(int i=3; i<=N; i+=2)
		if(!chae[i])
			Prime.push_back(i);
	int start = 0, end = 0, anscnt = 0, total = 0;
	while(1){
		if(total<N && end<Prime.size()){
			total += Prime[end];
			end++;
		}
		else{
			total -= Prime[start];
			start++;
		}
		if(total == N){
			anscnt++;
		}
		if(end > Prime.size() || start > end)
			break;	
	}
	printf("%d", anscnt);	
	}
}