[백준] 1644 소수의 연속합

May 18, 2021 ( last updated : May 18, 2021 )
투 포인터 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 1644번 소수의 연속합

[백준] 1644번 소수의 연속합

백준 1644번

알고리즘 유형

풀이방법

소수들을 먼저 구해줘야한다. N의 범위는 4000000까지가 최대이므로 40000000까지 에라토스테네스의 체 알고리즘을 통해서 소수들을 구해서 벡터 넣어둔다.

이후 low, high 두 수를 통해서 벡터 상에서 더해주는 값들의 시작 점과 끝 지점을 표현해 준다. 하나씩 이동하면서 벡터 내의 값들을 더하거나 빼면서 경우의 수를 카운트 해준다.

#include <algorithm>
#include <iostream>
#include <vector>

#define MAX (4000000 + 100)

using namespace std;

int N;
vector<int> prime;
long long numbers[MAX];
void set_prime_numbers() {

  for (long long i = 2; i < MAX; i++) {
    numbers[i] = i;
  }

  for (long long i = 2; i < MAX; i++) {
    if (numbers[i] == 0)
      continue;

    for (long long j = i * i; j < MAX; j += i) {
      if (j > MAX)
        continue;
      numbers[j] = 0;
    }
  }

  for (long long i = 2; i < MAX; i++) {
    if (!(numbers[i] == 0)) {
      prime.push_back(i);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N;
  set_prime_numbers();
  int low = 0, high = 0;
  int sum = prime[0];
  int cnt = 0;

  while (low <= high && prime[high] <= N) {
    if (sum < N) {
      sum += prime[++high];
    } else if (sum == N) {
      cnt++;
      sum += prime[++high];
    } else if (sum > N) {
      sum -= prime[low++];
    }
  }
  cout << cnt;
  return 0;
}

Originally published May 18, 2021
Latest update May 18, 2021

Related posts :

{# #}