[백준 1644] 소수의 연속합 (C#, C++) - soo:bak

문제 링크

1644번 - 소수의 연속합

설명

자연수 N을 연속된 소수들의 합으로 표현하는 방법의 수를 구하는 문제입니다. 예를 들어 41은 2+3+5+7+11+13, 11+13+17, 41 세 가지로 표현할 수 있습니다.

접근법

먼저 에라토스테네스의 체로 N 이하의 모든 소수를 구합니다.

다음으로 소수 배열에서 연속 구간의 합이 N인 경우를 세야 합니다. 투 포인터로 구간을 관리하면서, 합이 N보다 작으면 오른쪽을 확장하고 N 이상이면 왼쪽을 줄입니다.

이후 합이 정확히 N이 될 때마다 경우의 수를 증가시킵니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var isComp = new bool[n + 1];
      var primes = new List<int>();

      for (var i = 2; i * i <= n; i++) {
        if (isComp[i])
          continue;
        for (var j = i * i; j <= n; j += i)
          isComp[j] = true;
      }
      for (var i = 2; i <= n; i++) {
        if (!isComp[i])
          primes.Add(i);
      }

      var ans = 0;
      var sum = 0;
      var l = 0;
      var r = 0;
      while (true) {
        if (sum >= n) {
          sum -= primes[l++];
        } else {
          if (r == primes.Count)
            break;
          sum += primes[r++];
        }
        if (sum == n)
          ans++;
      }

      Console.WriteLine(ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<bool> vb;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vb comp(n + 1, false);
  vi primes;
  for (int i = 2; i * i <= n; i++) {
    if (comp[i])
      continue;
    for (int j = i * i; j <= n; j += i)
      comp[j] = true;
  }
  for (int i = 2; i <= n; i++) {
    if (!comp[i])
      primes.push_back(i);
  }

  int ans = 0, sum = 0, l = 0, r = 0;
  while (true) {
    if (sum >= n) {
      sum -= primes[l++];
    } else {
      if (r == (int)primes.size())
        break;
      sum += primes[r++];
    }
    if (sum == n)
      ans++;
  }

  cout << ans << "\n";

  return 0;
}