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

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

1644번: 소수의 연속합

 

문제 분석

어떤 자연수 N이 주어졌을 때 N을 나타낼 수 있는 소수의 연속합의 개수를 구하는 문제입니다. 에라토스테네스의 체를 이용하여 어떤 자연수 이하의 모든 소수를 구할 수 있고, 소수들이 자연스레 정렬되어 있기 때문에 투 포인터로 쉽게 문제를 해결할 수 있습니다.

 

코드

#include<iostream>
#include<vector>

using namespace std;

vector<bool> p(4000001, true);
vector<int> prime;
int N, s=0, e=0, sum=0, ans=0;

int main()
{
    cin>>N;

    for(int i=2; i<=N; i++)
    {
        if(p[i])
        {
            prime.push_back(i);
            for(int j=2; i*j<=N; j++)
            {
                p[i*j]=false;
            }
        }
    }

    prime.push_back(4000001); //N=4,000,000일 때 e가 범위를 벗어나서 참조하게 되므로 추가해줍니다.

    while(s<=e)
    {
        if(sum>=N || prime[e]>N)
        {
            sum-=prime[s];
            s+=1;
        }
        else
        {
            sum+=prime[e];
            e+=1;
        }

        if(sum==N) ans+=1;
    }

    cout<<ans;

    return 0;
}

 

문제 풀이

1. 에라토스테네스의 체로 400만 이하의 모든 소수를 구합니다.
2. 포인터 s(start)와 e(end)를 선언합니다. s와 e는 모두 0부터 시작합니다.
3. 소수의 연속합 sum을 선언하고 0으로 초기화합니다.
4. sum이 주어진 자연수 N보다 크거나 같다면 s가 가리키는 소수를 sum에서 빼고, s에 1을 더합니다.
5. sum이 주어진 자연수 N보다 작다면 e가 가리키는 소수를 sum에 더하고 e에 1을 더합니다. 하지만, e가 가리키는 소수가 N보다 크다면 소수합이 절대 N이 될 수 없으므로 4번 과정을 수행합니다.
6. sum이 주어진 자연수 N과 같다면 N을 연속된 소수합으로 나타낸 것입니다.
7. s가 e보다 커질 때까지 반복합니다.