1644 c++ - 소수의 연속합

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

여기에서 연속된 소수의 합이라고 해서 처음 접근법을 에라토스테네스의 체로 소수를 거르고, 소수들의 배열을 만들어서 누적합을 만드는 식으로 진행하였다. 에라토스테네스의 체의 수행시간은 O(nloglogn)이고 누적합 탐색 O(n^2)으로 시간초과에 걸렸다.

시간초과 누적합

#include <cmath>
#include <iostream>

using namespace std;

int n;
int pn[4000001];
int conPn[4000001];
int sumPn[4000001] = {0};

int primeNumberSieve() {
  for (int i = 2; i <= n; i++) {
    pn[i] = i;
  }

  for (int i = 2; i <= sqrt(n); i++) {
    if (pn[i] == 0) continue;
    for (int j = i * i; j <= n; j += i) pn[j] = 0;
  }

  int j = 0;
  for (int i = 2; i <= n; i++) {
    if (pn[i] != 0) conPn[j++] = pn[i];
  }

  for (int i = 0; i < j; i++) {
    sumPn[i + 1] = sumPn[i] + conPn[i];
  }

  return j;
}

int main() {
  cin >> n;
  int count = 0;
  int sumPnSize = 0;

  sumPnSize = primeNumberSieve();

  for (int i = 0; i < sumPnSize; i++) {
    for (int j = i + 1; j <= sumPnSize; j++) {
      if (sumPn[j] - sumPn[i] == n) {
        count++;
        break;
      }
    }
  }

  cout << count;

  return 0;
}

부분합의 누적합을 통해서 count를 세는 과정에서 누적합의 범위를 넘어가는 부분에서도 계속 체크를 해주고 있었기 때문에 시간 초과가 발생했다. 탐색 최적화를 통해 해결했다.

부분합(누적합)을 이용한 탐색 최적화 코드

#include <cmath>
#include <iostream>

using namespace std;

int n;
int pn[4000001];
int conPn[4000001];
int sumPn[4000001] = {0};

int primeNumberSieve() {
  for (int i = 2; i <= n; i++) {
    pn[i] = i;
  }

  for (int i = 2; i <= sqrt(n); i++) {
    if (pn[i] == 0) continue;
    for (int j = i * i; j <= n; j += i) pn[j] = 0;
  }

  int j = 0;
  for (int i = 2; i <= n; i++) {
    if (pn[i] != 0) conPn[j++] = pn[i];
  }

  for (int i = 0; i < j; i++) {
    sumPn[i + 1] = sumPn[i] + conPn[i];
  }

  return j;
}

int main() {
  cin >> n;
  int count = 0;
  int sumPnSize = 0;
  sumPnSize = primeNumberSieve();

  for (int i = 0; i < sumPnSize; i++) {
    for (int j = i + 1; j <= sumPnSize; j++) {
      if (sumPn[j] - sumPn[i] == n) {
        count++;
        break;
      } else if (sumPn[j] - sumPn[i] > n) {
        break;
      }
    }
  }

  cout << count;

  return 0;
}

 

투포인터를 활용한 탐색 최적화 코드 O(n)

투포인터의 원리는 누적합의 원리와 같고, 누적합을 구하지 않고도 해결할 수 있다.

#include <cmath>
#include <iostream>

using namespace std;

int n;
int pn[4000001];
int conPn[4000001];

int primeNumberSieve() {
  for (int i = 2; i <= n; i++) {
    pn[i] = i;
  }

  for (int i = 2; i <= sqrt(n); i++) {
    if (pn[i] == 0) continue;
    for (int j = i * i; j <= n; j += i) pn[j] = 0;
  }

  int j = 0;
  for (int i = 2; i <= n; i++) {
    if (pn[i] != 0) conPn[j++] = pn[i];
  }

  return j;
}

int main() {
  cin >> n;
  int count = 0;
  int conPnSize = 0;

  conPnSize = primeNumberSieve();

  int start = 0, end = 0, sum = 0;
  while (end <= conPnSize) {
    if (sum == n) {
      count++;
      sum -= conPn[start++];
    } else if (sum < n) {
      sum += conPn[end++];
    } else {
      sum -= conPn[start++];
    }
  }

  cout << count;

  return 0;
}