백준 1644번 소수의 연속합 ( C++ )

문제

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

 

해설

소수 구하는방법 외우기 + 시작점과 끝점 이용하는 방법도 고려해보기

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
int n, che[4000004], ret;
vector<int> arr;
 
bool go(int num)
{
  for (int i = 2; i <= sqrt(num); i++)
  {
    if (num % i == 0)
    {
      return false;
    }
  }
  return true;
}
 
int main()
{
  cin >> n;
  for (int i = 2; i <= n; i++)
  {
    if (che[i])
      continue;
    for (int j = i * 2; j <= n; j += i)
    {
      che[j] = 1;
    }
  }
  for (int i = 2; i <= n; i++)
  {
    if (!che[i])
      arr.push_back(i);
  }
 
  for (int i = 0; i < arr.size(); i++)
  {
    int tmp = 0;
    int j = i;
    while (tmp < n && j < arr.size())
    {
      tmp += arr[j++];
    }
    if (tmp == n)
      ret++;
  }
 
  cout << ret;
  return 0;
}