[백준 알고리즘] 1644번 소수의 연속 합

 

에라토스네테네스의 체 알고리즘을 기반으로 문제를 풀었다.

해당 알고리즘으로 n보다 작거나 같은 소수를 prime_list 벡터에 넣었다.

그 후 prime_list 끝부터 처음까지 순차적으로 값을 더하면서 탐색한다.

n과 같은지 확인하고 같으면 cnt를 1증가, 

n보다 크면 제일 큰 값을 sum에서 감소한다.

결과적으로 cnt값이 최종 결과값이다.

#include <iostream>
#include <vector>

using namespace std;

bool list[4000001];
int main(){
	int n;
	cin >> n;

	for(int i=2; i<=n; i++){
		if(list[i])
			continue;
		for(int j= i+i; j<=n; j+=i){
			list[j] = true;
		}
	}

	vector<int> prime_list;

	for(int i=2; i<=n; i++){
		if(!list[i])
			prime_list.push_back(i);
	}
	int pos = prime_list.size()-1;
	int sum = 0, cnt = 0;
	for(int i=pos; i>=0; i--){
		sum += prime_list[i];
		if(sum == n){
			cnt ++;
			sum -= prime_list[pos];
			pos --;
		}
		else if(sum > n){
			sum -= prime_list[pos];
			pos --;
		}	
	}
	
	cout << cnt;
	return 0;
}