백준 문제 1644번 소수의 연속합 문제풀이 c++

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

1644번: 소수의 연속합

문제

에라토스테네스의 체로 소수만 뽑아내서 v에 저장하고 그것으로 단순하게 2중 for문해도 풀렸다.

 

이렇게 풀어도 풀리는 이유는 400만까지의 소수가 대략 28만개이고 이렇게 이중 for문하면 28만*28만의 시간복잡도가 나오는데 400만이상에 대해서는 더 이상 연산하지않게 break를 걸기 때문에 총 연산횟수가 약 260만 정도기 때문에 충분히 시간 제한 내로 풀 수가 있었다. 

 

코드

#define MAX 4000001
#include <iostream>
#include <vector>
using namespace std;
vector <int> v;
int a[MAX];
int cnt[MAX];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    a[0]=1;
    a[1]=1;
    for(int i=2; i<MAX; i++)
    {
        for(int j=i+i; j<MAX; j=j+i)
        {
            a[j]=1;
        }
    }
    for(int i=1; i<MAX; i++)
    {
        if(a[i]==0)
        {
            v.push_back(i);
        }
    }
    for(int i=0; i<v.size(); i++)
    {
        int sum=0;
        for(int j=i; j<v.size(); j++)
        {
            sum=sum+v[j];
            if(sum>4000000)
            {
                break;
            }
            else
            {
                cnt[sum]++;
            }
        }
    }
    int n;
    cin>>n;
    cout<<cnt[n];
}