[백준] 1644번: 소수의 연속합 c++ 풀이 (에라토스테네스의 체, 투 포인터)

접근:

어떤 자연수가 주어지면 그것보다는 작은 소수의 합의 갯수를 구하는 것이므로,

n보다 작은 소수의 배열을 구하고, 그에 맞는 구간 합을 구하면 된다.

 

전략:

소수를 구하는 것은 에라스토테네스의 체를 이용하여 구하면 되고,

구간합은 투 포인터(two pointers)를 이용하여 구하면 된다.

 

코드:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> sosu; //n이하 소수 배열
bool so[4000001]; //소수 판별 배열
int n;
int sum = 0;
int s = 0, e = 0;
int res = 0;

int main(){
    cin >> n;
    
    for(int i=2;i<=n;i++){
        if(!so[i]){ //소수면
            sosu.push_back(i);
            for(int j=1; j*i <= n; j++){ //배수 삭제
                so[j*i] = true;
            }
        }
    }
    
    sum = 0;
    s=0, e=0;

    while(s<=e){ //2 pointer
        if(sum > n){
            sum -= sosu[s++];
        }
        else if(sum < n){
            if(e >= sosu.size()) break;
            sum += sosu[e++];
        }
        else{
            res++;
            if(e >= sosu.size()) break;
            sum += sosu[e++];
        }
    }

    cout << res << '\n';

    return 0;
}