[백준] 소수의 연속합

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

1644번: 소수의 연속합

우선 문제부터 간단하게 요약하면,

 

N이 주어지면, 연속된 소수의 합으로 N을 구성할 수 있는 경우의 수를 구해야 하는 문제입니다.

 

<Solution>

우선 N까지의 숫자들중 소수를 에라토스테네스의 체로 구합니다. 

 

그리고 이 소수들을 이용하여 누적합 배열을 만들어 두고, 총 몇개의 조합이 가능한지 투포인터 알고리즘을 이용하여 탐색하면 됩니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <vector>
#include <cmath>

#define MAX 4000000

using namespace std;

int N;
int isPrime[MAX+10];

vector <int> prime_number;
vector <int> prefix_sum;

int main(){
    cin >> N;

    // sieve of Eratosthenes
    for(int i = 2; i<=sqrt(N)+1; i++){
        if(isPrime[i]) continue;
        for(int j = 2*i; j <= N; j+=i){
            isPrime[j] = 1;
        }
    }
    for(int i = 2; i<=N; i++){
        if(isPrime[i]) continue;
        prime_number.push_back(i);
    }

    // build prefix sum vector
    prefix_sum.push_back(0);
    for(int i : prime_number){
        prefix_sum.push_back(prefix_sum.back() + i);
    }

    // two pointer
    int sIndex =0, eIndex = 0;
    int curSum = 0;
    int ans = 0;

    while(eIndex <= prefix_sum.size()){
        curSum = prefix_sum[eIndex]-prefix_sum[sIndex];

        if(curSum < N) eIndex++;
        else if (curSum > N) sIndex++;
        else {
            ans++; 
            eIndex++;
        }
    }

    cout << ans << endl;
    return 0;

}