BOJ 1644 소수의 연속합

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

문제

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

• 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

---

예제 입력 1

20

예제 출력 1

0

예제 입력 2

3

예제 출력 2

1

… 이하 예제 생략

---

코드

문제를 읽었을 때, 소수들을 알고 있다면 투 포인터를 사용해서 연속된 소수의 합으로 N을 나타낼 수 있는 경우의 수를 계산해낼 수 있다고 생각했다.

문제는 소수들을 구할 방법인데, 예전에 에라토스테네스의 체로 소수들을 구하는 문제를 풀어본 적이 있어서 쉽게 문제를 풀 수 있었다.

에라토스테네스의 체 문제를 푼 기록을 찾아봤는데, 거의 2년 전에 풀었던 문제였다.

상당히 오래 됐는데 아직 기억하고 있는 걸 보니, 그 때 당시에는 풀이 방식이 꽤 인상적이었던 모양이다.

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

public class Main {

    static int N;
    static List<Integer> primeNumbers = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        initializePrimeNumbers();

        int answer = countCases();

        System.out.println(answer);
    }

    static void initializePrimeNumbers() {
        boolean[] isNotPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++) {
            if(isNotPrime[i]) {
                continue;
            }

            for (int j = i * 2; j <= N; j += i) {
                isNotPrime[j] = true;
            }
        }

        for (int i = 2; i <= N; i++) {
            if(!isNotPrime[i]) {
                primeNumbers.add(i);
            }
        }
    }

    static int countCases() {
        int count = 0;
        int leftIdx = 0;
        int rightIdx = 0;
        int sum = 0;
        primeNumbers.add(0);

        while (rightIdx < primeNumbers.size()) {
            if(sum == N) {
                count++;
            }

            if(sum <= N) {
                sum += primeNumbers.get(rightIdx);
                rightIdx++;
            } else {
                sum -= primeNumbers.get(leftIdx);
                leftIdx++;
            }
        }

        return count;
    }
}