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

문제 링크 : https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

>풀이

에라토스테네스의 체(소수 구하기) 알고리즘 과, 투포인터 알고리즘을 사용

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
        int N;
        vector<bool> check;
        vector<int> prime;

        scanf("%d", &N);
        check.resize(N + 1, true);

        for (int i = 2; i * i <= N; i++) {
                if (check[i] == true) {
                        for(int j = i + i; j <= N; j += i)
                                check[j] = false;
                }
        }

        for (int i = 2; i < N + 1; i++) {
                if (check[i] == true) 
                        prime.push_back(i);
        }

        int cnt = 0, high = 0, low = 0, sum = 0;
        while (1) {
                if (sum >= N)
                        sum -= prime[low++];
                else if (high == prime.size())
                        break;
                else
                        sum += prime[high++];

                if (sum == N) cnt++;
        }
        printf("%d", cnt);
        return 0;
}

(개발 환경 : vs code)