백준 / 1644 소수의 연속합 C++

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

온라인 컴파일러로 돌려서 좀 삐리했는데 잘 통과했습니다 ㅎㅎㅎ

빨리 서울로 올라가서 텐서랑 정처기 공부를 해야할 거 같습니다. 집에서는 공부가 안 돼....

 

해당 수를 연속된 소수의 합으로 표현할 수 있는 경우의 수를 구해라는 문제입니다.

에라토스테네스 체를 이용하여 주어진 범위 내의 소수를 모두 구한 후, 투 포인터를 이용해 풀었습니다.

start index = 0, end index = 1로 잡은 뒤, 해당 수 n과 start~end의 합이 일치하면 result+=1, 

합이 작으면 end+=1, n이 작으면 start+=1 을 하며 비교하면 됩니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
bool check[4000001];
vector<int> prime;

void make_prime()
{
    memset(check, true, sizeof(check));
    check[0] = false;
    check[1] = false;
    
    for(int i=2;i<=4000000;i++){
        if(check[i]){
            for(int j=2*i;j<=4000000;j+=i)
                check[j]=false;
            prime.push_back(i);
        }
    }
}

int cal_sum(int start, int end)
{
    int ans = 0;
    for(int i=start;i<=end;i++){
        ans += prime[i];
    }
    return ans;
}

int main()
{
    cin >> n;
    make_prime();
    int result = 0;
    
    if(check[n])
        result++;
    
    int start = 0;
    int end = 1;
    
    while(1){
        if(prime[start]>(n/2 + 1))
            break;
        
        int prime_sum = cal_sum(start, end);
        
        if(n==prime_sum){
            result++;
            start++;
            end++;
        }
        
        else if(n<prime_sum){
            start++;
        }
            
        else if(n>prime_sum){
            end++;
        }
    }
    
    cout << result;
}