[BOJ 1644] 소수의 연속합

🔗Link

문제
풀이

💡Idea

에라토스테네스의 체를 이용하여 소수를 효율적으로 구하고, 소수들을 투 포인터로 순회하며 합이 N이 되는 경우의 수를 찾으면 된다.

🔑Code

#include <bits/stdc++.h>
using namespace std;

int N;
bool isPrimeNumber[4'000'001];
vector<int> primeNums;

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    // 아리토스테네스의 체
    fill(isPrimeNumber+2, isPrimeNumber+N+1, true);
    for(int i = 2; i*i <= N; i++){
        if(!isPrimeNumber[i]) continue;
        for(int j = i*i; j <= N; j += i){
            isPrimeNumber[j] = false;
        }
    }
    for(int i = 2; i <= N; i++){
        if(!isPrimeNumber[i]) continue;
            primeNums.emplace_back(i);
    }

    int cur = 0, ans = 0;
    auto r = primeNums.begin(), l = primeNums.begin();
    for(; r != primeNums.end(); r++){
        cur += *r;
        while(cur > N && l != primeNums.end()){
            cur -= *l;
            l++;
        }
        if(cur == N) ans++;
    }

    cout << ans;

    return 0;
}

🗨️ Side Notes

투 포인터의 시간복잡도는 O(N)이다.