[백준/C++] 알고리즘 1644번 소수의 연속합

오늘은 백준 알고리즘 1644번 소수의 연속합문제에 대해 알아보도록 하겠습니다

​

문제부터 보겠습니다.

​

​

이 문제는 소수구하기 + 투포인터가 결합된 문제입니다.

개념이랑 기본코드만 알고있으면 쉽게 풀수 있는 문제입니다.

소수를 구하는 방법은 여러가지가 있겠지만 에라토스테네스의 체라는 방식을 이용하여 구현을 합니다.

왜냐하면 이 방법의 시간복잡도가 O(root(n))이기 때문입니다.

​

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> a;
int  number;
long long a1[4000001];
// 에라토스테네스의 체
void primeNumber(){
 for (int i = 2; i <= number; i++)
      a1[i] = i;    
    for (int i = 2; i <= sqrt(number); i++)
    {
        // primeNum[i] 가 0이면 이미 소수가 아니므로 continue
        if (a1[i] == 0)
            continue;
        // i*k (k<i) 까지의 수는 이미 검사했으므로 j는 i*i 부터 검사해준다.
        for (int j = i * i; j <= number; j += i)
            a1[j] = 0;
    }

  for (int i = 2 ; i <= number ; i++){
    if(a1[i]) a.push_back(i);
  }
  }

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   cin>>number;
    primeNumber();

    
  int left = 0;
  int right = 0;
  int sum = a[0];
int ans = 0;
while (left <= right && right < a.size()) {

if(sum<number){ right += 1;
sum += a[right];
} else if (sum == number) {
    ans += 1;
    right += 1;
    sum += a[right];
   } else if (sum > number) {
    sum -= a[left++];
   if (left > right && left < a.size()) {
  right = left;
sum = a[left];
 } }
  }


      cout <<ans<< '\n';
    return 0;
 
  }

​

긴 글 읽어주셔서 감사합니다.