소수의 연속합 1644

문제

접근 방법

소수들을 구해놓고 범위를 넓히고 좁히며 해결하면 된다고 생각했다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int N, cnt = 0, sum = 0;
    cin >> N;
    vector<bool> isPrime(N + 1, true);
    vector<int> primeNum;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= N; ++i)
        for (int j = (i << 1); j <= N; j += i)
            isPrime[j] = false;
    for (int i = 2; i <= N; ++i)
        if (isPrime[i])
            primeNum.push_back(i);
    for (int start = 0, end = 0; end < primeNum.size(); ++end)
    {
        sum += primeNum[end];
        while (sum > N)
            sum -= primeNum[start++];
        if (sum == N)
            ++cnt;
    }
    cout << cnt;
    return 0;
}

풀이

아리토네스의 체를 활용하여 범위 내의 소수들을 구한다. 그 후 소수들을 차례대로 더해가며 목표 자연수 N보다 클 시 소수를 앞에서부터 줄여가는 형식으로 풀면 된다.