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

문제

 

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

---

Algorithm

모르면 너무 어렵고 알면 너무 쉬운 문제이기에 출제 시 변별력이 굉장히 강하면서도, 
소수 판정 + 투 포인터 태그 중 굉장히 교육적인 문제라고 생각되어 소개한다.

연속된 소수의 합으로만 이루어져 있어야하므로, 에라토스테네체의 체를 활용해 N까지의 소수를 담은 배열을 만들어야 한다.

• 에라토스테네체는 연속된 소수 판별의 대표적인 알고리즘이다.
  
  

void Eratos(int num)
{
    // 에테체
    for(int i = 2; i*i <= num; i++)
    {
        if(!visited[i])
        {
            for(int j = 2; i*j <= num; j++)
            {
                visited[i*j] = true;
            }
        }
    }
}

 

위 코드와 같이, 2 이상이고 num 이하인 i에 대하여, 자신을 제외하고 i가 약수가 되는 모든 num이하의 수를 표기함으로써 소수가 아닌 수를 구별한다.

이후, i가 2 이상인 visited[i] 가 false인 수. 즉, 소수를 배열에 담아 투 포인터를 진행하게 된다.
배열은 오름차순 정렬되어 있으므로, left부터 right까지의 합이 n보다 작으면 right를 이동하고 n보다 크다면 left를 이동해 합을 갱신한다.
이 과정을 반복하는 동안, 합과 n이 같아지는 횟수가 출력 답안이 된다.

이때, n이 1인경우 예외처리 해주어야 함에 주의하자.

---

 

 

Code

#include <iostream>
#include <vector>
using namespace std;

int n;
bool visited[4000001];
vector<int> pN;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
}

void Eratos(int num)
{
    // 에테체
    for(int i = 2; i*i <= num; i++)
    {
        if(!visited[i])
        {
            for(int j = 2; i*j <= num; j++)
            {
                visited[i*j] = true;
            }
        }
    }
}

int TP()
{
    int ans = 0;

    int start = 0,end = 0, sum = pN[0];
    while(end < pN.size())
    {
        if(sum <= n)
        {
            if(sum == n) ans++;
            sum += pN[++end];
        }
        else
        {
            if(start == end)
            {
                start++; end++;
                sum = pN[start];
            }
            else sum -= pN[start++];
        }
    }
    return ans;
}

void SOLVE()
{
    if(n == 1) cout << 0, exit(0);

    Eratos(n);

    for(int i = 2; i <= n; i++)
        if(!visited[i])
            pN.push_back(i);

    cout << TP();
}

int main()
{
    INPUT();
    SOLVE();
}