[Algorithm] 1644: 소수의 연속합

📦1644: 소수의 연속합

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-20
문제 확인하기

풀이

• 연속된 소수의 합으로 목표값을 만드는 방식이기 때문에 소수를 먼저 구해 vector 안에 저장한다.
• 투포인터 방식으로 늘리고 줄이면서 목표값에 도달하는 경우 res++ 을 통해서 목표값을 만들 수 있는 횟수를 구한다.

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;
 
int n, sum=0, res;
vector<int> vec;
 
void Input(){
    cin >> n;
    if(n == 1){
        cout << 0 << endl;
        exit(0);
    }
}
 
void eratos(int n){
    vector<int> prime(n+1, 1);
 
    for(int i=2; i*i<=n; ++i){
        if(prime[i]){
            for(int j=i*i; j<=n; j+=i){
                prime[j] = 0;
            }
        }
    }
    for(int i=2; i<=n; ++i){
        if(prime[i]) vec.push_back(i);
    }
}
 
void Solution(){
    eratos(n);
    int start = 0; 
    int end = 0;
    res = 0;
    while(start<=end && end<=vec.size()){
        if(sum < n){
            sum+=vec[end];
            end++;
        }
        else{
            sum-=vec[start];
            start++;
        }
        if(sum == n) res++;
    }
    cout << res << endl;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    Input();
    Solution();
 
    return 0;
}