[백준/CPP/JS] 1644번. 소수의 연속합

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

1. 문제

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

• 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과 같은 표현도 적합하지 않다.

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

2. 입력

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

3. 출력

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

4. 풀이

• 투포인터 기본 문제인 수들의 합2와 풀이가 같다.
• 숫자 배열이 주어지지 않고 소수의 배열을 직접 구해서 사용해야 한다.
• 에라토스테네스의 체를 이용해서 소수 배열을 구해주었다.
• 그 외 풀이는 수들의 합2와 같다.

5. 코드 - cpp

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

using namespace std;

vector<int> getPrimeNums(int n)
{
  vector<int> result;
  vector<bool> nums(n + 2, true);

  for (int i = 2; i * i <= n; i++)
    if (nums[i])
      for (int j = i * i; j <= n; j += i)
        nums[j] = false;

  for (int i = 2; i <= n; i++)
    if (nums[i])
      result.push_back(i);

  return result;
}

int main()
{
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int answer = 0;
  int n;
  cin >> n;
  vector<int> primeNums = getPrimeNums(n);

  int lt = 0;
  int sum = 0;
  for (int rt = 0; rt < primeNums.size(); rt++)
  {
    sum += primeNums[rt];
    while (n < sum)
      sum -= primeNums[lt++];

    answer += sum == n ? 1 : 0;
  }

  cout << answer;
}

6. 코드 - js

function getPrimeNums(n) {
  let result = [];
  let nums = Array(n + 2).fill(true);

  for (let i = 2; i * i <= n; i++) {
    if (nums[i]) {
      for (let j = i * i; j <= n; j += i) {
        nums[j] = false;
      }
    }
  }

  for (let i = 2; i <= n; i++) {
    if (nums[i]) result.push(i);
  }
  return result;
}

function solution(n) {
  let answer = 0;
  let pirmeNums = getPrimeNums(n);

  let left = 0;
  let sum = 0;

  for (let right = 0; right < pirmeNums.length; right++) {
    sum += pirmeNums[right];

    while (n < sum) {
      sum -= pirmeNums[left++];
    }
    answer += sum === n ? 1 : 0;
  }

  return answer;
}