백준 1644번 소수의 연속합

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

에라토스테네스의 체와 투 포인터 알고리즘을 적용하면 쉽게 풀 수 있는 문제였습니다.

에라토스테네스의 체를 적용할 때 i * i의 범위가 int 범위를 초과하므로 long long으로 반복문을 돌려야하는 것이 핵심이였습니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 4000000;

 

long long minFactor[MAX];

vector<int> prime;

 

//에라토스테네스의 체

void eratosthenes(void)

{

        minFactor[0] = minFactor[1] = -1;

        for (long long i = 2; i < MAX; i++)

                 minFactor[i] = i;

 

        for (long long i = 2; i < MAX; i++)

                 if (minFactor[i] == i)

                         for (long long j = i * i; j < MAX; j += i)

                                 if (minFactor[j] == j)

                                          minFactor[j] = i;

 

        for (int i = 2; i < MAX; i++)

                 if (minFactor[i] == i)

                         prime.push_back(i);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        eratosthenes();

        int low = 0, high = 0;

        int sum = prime[0];

        int result = 0;

        //투 포인터 알고리즘 적용

        while (low <= high && high < prime.size() && prime[low] <= N)

        {

                 if (sum < N)

                         sum += prime[++high];

                 else if (sum == N)

                 {

                         result++;

                         sum += prime[++high];

                 }

                 else if (sum > N)

                 {

                         sum -= prime[low++];

                         if (low > high && low < prime.size())

                         {

                                 high = low;

                                 sum = prime[low];

                         }

                 }

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~