[BOJ] 1644 - 소수의 연속합

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

BOJ - 소수의 연속합

문제 유형: 수학, 정수론, 슬라이딩 윈도우

문제 난이도: Gold III

시간 제한: 2초

메모리 제한: 128MB

 

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

 

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

풀이

우선, 에라토스테네스의 체를 이용해서 소수들만 따로 배열에 순차적으로 담는다.

슬라이딩 윈도우를 이용해서 오른쪽으로 확장하면서 구간합을 늘린다.

만약 합이 n이상이라면 왼쪽을 밀어서 합을 줄여본다. 만약 정확히 n이라면, 개수를 1 추가한다.

 

최종적인 개수를 출력한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n;

int main(int argc, char *argv[]) {
  cin >> n;

  vector<bool> sieve(n + 1, true);
  vector<int> primes;
  sieve[0] = false;
  sieve[1] = false;
  for (int i = 2; i <= n; ++i) {
    if (!sieve[i])
      continue;
    primes.push_back(i);
    for (int j = i; j <= n; j += i) {
      sieve[j] = false;
    }
  }

  int left = 0;
  int m = primes.size();
  int sum = 0;
  int ans = 0;
  for (int right = 0; right < m; ++right) {
    sum += primes[right];
    while (left <= right && sum >= n) {
      if (sum == n)
        ans++;
      sum -= primes[left];
      left++;
    }
  }

  cout << ans << "\n";

  return 0;
}