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

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

 

에라토스테네스의 체를 이용해서 소수만 들어가있는 배열을 만들고 그 배열에서 투 포인터를 이용해서 누적합이 n보다 작으면 오른쪽 포인터를 증가시키고 반대면 왼쪽 포인터를 증가시키면서 누적합이 n과 같은 경우의 수들을 찾았다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;

vector<bool> isPrime;
vector<int> primes;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    isPrime = vector<bool>(n + 1, true);


    isPrime[0] = false;
    isPrime[1] = false;

    for (int i = 2; i <= sqrt(n); i++) {
        if (!isPrime[i])
            continue;
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i])
            continue;
        primes.push_back(i);
    }
    if (primes.size() == 0) {
        cout << 0;
        return 0;
    }
    int sum = primes[0];
    int left = 0;
    int right = 0;
    int cnt = 0;
    while (right < primes.size()) {
        if (sum == n) {
            cnt++;
            sum -= primes[left];
            left++;
            right++;
            if (right < primes.size())
                sum += primes[right];
        }
        else if (sum < n) {
            right++;
            if (right < primes.size())
                sum += primes[right];
        }
        else {
            sum -= primes[left];
            left++;
        }
    }
    cout << cnt;
}