문제

소수의 연속합 - 골드 3

---

문제 이해

• 소수들을 구한다.
• 소수들을 기반으로 투 포인터 알고리즘을 수행하여 해당 값을 표현할 수 있는 개수를 센다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Baekjoon_1644 {
  static int N;
  static boolean[] isPrime;
  static int count;
  static List<Integer> primeSet = new ArrayList<>();

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    isPrime = new boolean[N + 1];
    // 에라토스테네스의 체 사용
    setPrime();
    twoPointer();
    System.out.println(count);
  }

  // 에라토스테네스의 체
  static void setPrime() {
    for (int i = 2; i * i <= N; i++) {
      for (int j = i * i; j <= N; j += i) {
        isPrime[j] = true;
      }
    }
    for (int i = 2; i <= N; i++)
      if (isPrime[i] == false)
        primeSet.add(i);
  }

  static void twoPointer() {
    int sum = 0;
    int start = 0;
    int end = 0;
    while (true) {
      if (sum >= N)
        sum -= primeSet.get(start++);
      else if (end == primeSet.size())
        break;
      else
        sum += primeSet.get(end++);

      if (sum == N)
        count++;
    }
  }
}

---

코드 설명

먼저 N을 입력받아서 (N+1)개의 배열을 선언한다. -> 소수 판별(isPrime)
에라토스테네스의 체 알고리즘을 이용하여 소수들을 판별한다.
판별된 소수들을 List에 저장한다. -> primeSet
판별된 소수들을 기준으로 투 포인터 알고리즘을 수행하여 합이 N이 되는 개수를 구한다.

---