1644번

1644번 - 소수의 연속합

1806번과 비슷한 문제인데, 소수라는 점만 바뀌었다.

소수를 구하는 방법은 에라토스테네스의 체를 이용해서 구했다.

그 다음 left , right 를 이용해서 필요없는 계산을 최대한 줄여서 경우의 수를 구했다.

실수한 점

->  처음에 에라토스테네스의 체의 첫번째 for문을  i*i<=4000001; 로 하고, prime.push_back(i) 를 하다보니,

     

3999971 같은 큰 소수는 isPrime 이 true 로 되어있지만, prime 벡터에는 들어가지 않았다.

for문을 i<=4000001; 로 하거나, 따로 for문을 만들어서 isPrime==true 면 벡터에 담는 방식으로 풀어야 한다.

<정답 코드>

#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
 
bool isPrime[4000005];
vector<int> prime;
void era(int n)
{
    for (int i = 2; i <= 4000001; i++)
    {
        if (isPrime[i])
        {
            prime.push_back(i);
            for (int j = i*2; j<= 4000001; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
 
}
 
int main()
{
    int n;
    scanf("%d", &n);
    memset(isPrime, true, sizeof(isPrime));
    //에라토스테네스의 체
    era(n);
 
    int left = 0, right = 0, cnt = 0, sum = 0;
 
    while (left <= right && right < prime.size())
    {
        if (sum < n)
        {
            sum += prime[right++];
        }
        else if (sum == n)
        {
            cnt++;
            sum += prime[right++];
        }
        else if (sum > n)
        {
            sum -= prime[left++];
        }
    }
 
 
    printf("%d\n", cnt);
    return 0;
}