(1644) 소수의 연속합

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

단계별로 풀어보기

30단계(투 포인터) 4번째

 

 

 

이전 문제와 비슷하지만, 배열이 입력에서 주어지는 대신 연속된 소수로 이루어진다. 소수 배열은 예전에 썼던 에라토스테네스의 체를 이용하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n;
  
  cin >> n;
  
  if(n==1){
    cout << 0;
    
    return 0;
  }
  
  vector<int> v;
  bool soe[4'000'001]= {true, true, false, };
  
  for(int i=4;i<=n;i+=2)  soe[i]= true;
  for(int i=3;i*i<=n;i+=2){
    if(soe[i])  continue;
    
    for(int j=i;i*j<=n;j+=2)  soe[i*j]= true;
  }
  
  for(int i=2;i<=n;i++){
    if(!soe[i])  v.push_back(i);
  }
  
  int s= 0, e= 0, acc= v[0], ans= 0;
  
  while(s<=e){
    if(acc>=n){
      if (acc==n)  ans++;
      
      acc-= v[s++];
    }else{
      if(e==v.size()-1)  break;
      
      acc+= v[++e];
    }
  }
  
  cout << ans;
  
  return 0;
}