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

96%에서 자꾸 틀려서 뭐가 문제일까 고민해봤더니

2를 넣었을 때 0이 나왔다.

 

---

소수의 연속합!

꽤나 간단한 문제이다.

 

여태까지 공부한 내용들을 합치면 되었는데

 

일단 에라토스테네스의 체를 이용해 입력된 N까지의 소수를 구한다.

int primeNumArr[4000001];
vector<int> primeNums;

// 소수 구하기
void primeNumSieve(int n)
{
    // primeNum 배열 초기화
    for (int i = 2; i <= n; ++i)
    {
        primeNumArr[i] = i;
    }

    for (int i = 2; i <= sqrt(n); ++i)
    {
        if (primeNumArr[i] == 0)
            continue;

        for (int j = i * i; j <= n; j += i)
            primeNumArr[j] = 0;
    }

    for (int i = 2; i <= n; ++i)
    {
        if (primeNumArr[i] != 0)
        {
            primeNums.push_back(i);
        }
    }
}

 

그 후 두 포인터를 활용해 위에서 구했던 소수들의 연속합을 구해서

N과 같은 값이 나오는 것들을 카운팅해준다.

 

int answer = 0;
    int temp = 2, arrSize = primeNums.size();
    int left = 0, right = 0;
    while (right < arrSize - 1)
    {
        if (temp < n)
        {
            //값이 N보다 작다면 라이트를 올리고 더한다
            temp += primeNums[++right];
        }
        else if (temp == n)
        {
            temp -= primeNums[left++];
            answer++;
        }
        else
        {
            //값이 N보다 크다면 left를 뺴주고 1올린다
            temp -= primeNums[left++];
        }
    }

    while (left < right)
    {
        temp -= primeNums[left++];
        if (temp == n)
            answer++;
    }

약간 실수를 해서 2를 넣었을 때는 카운팅이 안 되는데

그 부분은 if문으로 체크했다.

 

[ 전체 코드 ]

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int primeNumArr[4000001];
vector<int> primeNums;

// 소수 구하기
void primeNumSieve(int n)
{
    // primeNum 배열 초기화
    for (int i = 2; i <= n; ++i)
    {
        primeNumArr[i] = i;
    }

    for (int i = 2; i <= sqrt(n); ++i)
    {
        if (primeNumArr[i] == 0)
            continue;

        for (int j = i * i; j <= n; j += i)
            primeNumArr[j] = 0;
    }

    for (int i = 2; i <= n; ++i)
    {
        if (primeNumArr[i] != 0)
        {
            primeNums.push_back(i);
        }
    }
}

int main()
{
	int n;
	cin >> n;
    primeNumSieve(n);

    int answer = 0;
    int temp = 2, arrSize = primeNums.size();
    int left = 0, right = 0;
    while (right < arrSize - 1)
    {
        if (temp < n)
        {
            //값이 N보다 작다면 라이트를 올리고 더한다
            temp += primeNums[++right];
        }
        else if (temp == n)
        {
            temp -= primeNums[left++];
            answer++;
        }
        else
        {
            //값이 N보다 크다면 left를 뺴주고 1올린다
            temp -= primeNums[left++];
        }
    }

    while (left < right)
    {
        temp -= primeNums[left++];
        if (temp == n)
            answer++;
    }

    if (n == 2)
    {
        cout << 1;
        return 0;
    }
    cout << answer;
}