[백준 1644번] 소수의 연속합

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

1644번: 소수의 연속합

<문제 풀이> 에라토스테네스의 체, 투 포인터

 

에라토스테네스의 체로 N이하의 소수를 모두 구하고 투 포인터 알고리즘으로 부분합을 구해주면 쉽게 풀 수 있습니다

 

<C++ 소스 코드>

#include <iostream>
#include <vector>
using namespace std;
 
bool visited[4000001];
bool is_prime[4000001];
vector<int> plist;
int n;
void eratosthenes() {
    for (int i = 2; i <= n; i++) is_prime[i] = true;
    for (int i = 2; i * i <= n; i++) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    eratosthenes();
    for (int i = 2; i <= n; i++) if (is_prime[i]) plist.push_back(i);
    int s = 0, e = 0, res = 0, sum = 0;
    int psize = plist.size();
    while (true) {
        if (sum == n) res++;
        if (sum >= n) sum -= plist[s++];
        else if (e == psize) break;
        else sum += plist[e++];
    }
    cout << res;
 
    return 0;
}