백준 1644 / 소수의 연속합

일단 n 이하의 소수를 모두 구해놓으면

 

투 포인터스 알고리즘을 통해 O(n)만에 답을 구할 수 있지만

n의 제한이 400만이기 때문에 

400만 이하의 소수를 모두 구하는 것은 빠른 시간내에 불가능하다.

400만이하의 어떤수 i를 2부터 루트 i까지 나누어 본 다음, 나눠지지 않으면 소수로 판별하는 알고리즘이 있지만

이마저도 느리다.

해답은 에라토스테네스의 체

어떤 소수를 구하면 그 소수의 배수들을 모두 체크하는 방법이다.

에라토스테네스의 체를 사용하면 빠르게 해결가능하다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<memory.h>
 
using namespace std;
 
vector<int>sosu;
bool issosu[4000005];
 
int main() {
    int num;
 
    cin >> num;
 
    memset(issosu, true, sizeof(issosu));
 
 
    for (int i = 2; i <= 4000000; i++) {
 
        if (issosu[i] == true) {
            sosu.push_back(i);
            for (int j = i * 2; j <= 4000000; j += i) {
                issosu[j] = false;
            }
        }
    }
 
 
 
    int right = 0; int left = 0;
    int sum = sosu[0];
    int ans = 0;
 
    while (left <= right && right < sosu.size()-1) {
 
        if (sum < num) {
            if (right <sosu.size()-1) {
                right++;
                sum += sosu[right];
            }
        }
        if (sum > num) {
            if (left <= right) {
                sum -= sosu[left];
                left++;
            }
        }
 
        if (sum == num) {
            ans++;
            if (right < sosu.size() - 1) {
                right++;
                sum += sosu[right];
            }
        }
    }
 
 
    cout << ans;
 
 
}