백준 1644 소수의 연속합

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 어떤수가 연속된 소수의 합으로 이루어 질 수 있는 경우의 수를 출력하는 문제입니다.

 

에라토스테네스의 체를 이용하여 소수들을 판별하고 그 소수를 모두 벡터에 집어넣은 뒤

 

첫번째 소수부터 계속 더해가며 그 숫자가 나오는 배열의 인덱스 값을 증가 시켰습니다.

 

총 범위가 4000000 이고 소수의 개수가 28만개 정도 나와서 시간초과가 날거 같았는데 합이 4000000을 넘으면 의미가 없어지므로 탈출하는 조건을 넣어 주어서 그런지 통과가 되었습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>

#define MAX 4000001

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int *prime = new int[MAX];
	fill_n(prime, MAX, 1);
	vector<int> v;
	int result;
	prime[0] = 0;
	prime[1] = 0;
	
	for(int i = 2; i < MAX; i++)
		if(prime[i]) {
			v.push_back(i);
			for(int j = i+i; j < MAX; j+=i)
				prime[j] = 0;		
		}
	
	int len = v.size();
	cout << len;
	for(int i = 0; i < len; i++) {
		result = v[i];
		for(int j = i+1; j < len; j++) {
			result += v[j];
			if(result > 4000000)
				break;
			
			prime[result]++;
			
		}
	}
	
	int N; cin >> N;
	cout<<prime[N];
	
	return 0;
	
}