[백준 c++] 1644 소수의 연속합

문제 설명

풀이

1. 소수 판별하는 bool array 만들기 (0:소수 1:소수 아님)
   어떤 수가 소수라면 그 수를 포함하는 더 큰 수들은 모두 소수가 아니라는 것을 이용한다.

   for (int j = 2 * i; j <= n; j += i)
         prime[j] = 1;

2. prime 배열에서 소수만 vector hol 에 삽입
3. 연속합은 자기 자신 또는 여러 수로 이루어진다. 여러 수로 이루어질 때는 그 수들이 연속적이어야 한다. 따라서 n에서 보다 작은 소수를 뺀 값이 그 다음 idx의 소수보다 크거나 같아야 한다. n - hol[i] >= hol[i+1]

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, cnt;
vector<int> hol;
bool prime[4000001];

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        if (prime[i])
            continue;
        for (int j = 2 * i; j <= n; j += i)
        {
            prime[j] = 1;
        }
    }
    for (int i = n; i > 1; i--)
    {
        if (!prime[i])
            hol.push_back(i);
    }

    for (int i = 0; i < hol.size(); i++)
    {
        int next = n;
        if (next == hol[i])
        {
            cnt++;
            continue;
        }
        if (next - hol[i] >= hol[i + 1])
        {
            int j = i;
            while (j < hol.size())
            {
                if (next == hol[j])
                {
                    cnt++;
                    break;
                }
                if (next - hol[j] < hol[j + 1])
                    break;
                next -= hol[j];
                j++;
            }
        }
    }
    cout << cnt << "\n";
}