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

문제 링크

---

1644번: 소수의 연속합

접근 방법

---

N까지의 소수를 먼저 구한 다음, 연속된 소수의 합을 구합니다.

소스 코드

---

#include <iostream>
#include <vector>

using namespace std;

vector<int> prime;
int n;

void eratosthenes() // 에라토스테네스의 체로 소수를 구합니다.
{
    vector<int> isPrime(n + 1, true);
    long long tmp = (long long)n;
    isPrime[0] = isPrime[1] = false;

    for (long long p = 2; p * p <= tmp; p++) // N이 4,000,000 이기 때문에 제곱하면 int 범위를 벗어나므로 long long으로 함
    {
        if (isPrime[p])
        {
            for (long long i = p * p; i <= tmp; i += p)
                isPrime[i] = false;
        }
    }

    for (int i = 2; i <= n; i++)
        if (isPrime[i])
            prime.push_back(i);
    prime.push_back(0);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    size_t s = 0, e = 0, maxIdx;
    int sum = 0, cnt = 0;
    prime.reserve(283147);
    cin >> n;

    eratosthenes();
    maxIdx = prime.size() - 1;

    while (s <= maxIdx && e <= maxIdx)
    {
        if (sum < n) // n 보다 합이 작으면 수를 더해줌
            sum += prime[e++];
        
        else if (sum == n) // n과 같으면 먼저 더해줬던 수를 빼줌
        {
            ++cnt;
            sum -= prime[s++];
        }

        else
            sum -= prime[s++]; // n 보다 크면 먼저 더해줬던 수를 빼줌
    }

    cout << cnt;

    return 0;
}

코드 설명

---

n이 최대 4,000,000 이므로 에라토스테네스의 체를 사용해서 소수를 구할 때 int 범위를 벗어납니다.

따라서 long long으로 for 문을 초기화합니다. 4,000,000으로 만들 수 있는 소수의 최대 개수는 283146입니다.

백터의 공간을 먼저 할당하면 push_back의 속도가 빨라집니다. 따라서 먼저 공간을 할당합니다.

43번째 while문에서 s나 e가 최대 prime의 size만큼 갈 수 있기 때문에 소수의 최대 개수보다 1만큼 크게 만들어준 다음, 마지막에 결과에 영향을 미치지 않는 0을 넣어줍니다.

연속된 소수의 합이 n 보다 작으면 소수를 더해주며, n과 같으면 cnt에 1을 더해주며, n과 크거나 같으면 먼저 더해준 소수를 빼줍니다.

유사 문제

---

[백준 C++] 1806. 부분합