🧩문제 설명

자연수 N이 주어졌을 때,
N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제입니다.

예를 들어,
N = 41이라면 아래와 같이 3가지 방법이 있습니다:

2 + 3 + 5 + 7 + 11 + 13 = 41  
11 + 13 + 17 = 41  
41 = 41

➡ 결과: 3

🧠 풀이 아이디어 (중요)

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

구한 소수를 연속된 부분합으로 탐색하며, 그 합이 N이 되는 경우의 수를 센다.

부분합 탐색은 투 포인터(two-pointer) 방식으로 효율적으로 처리한다.

⚙️ 알고리즘 흐름

1️⃣ 소수 구하기 (에라토스테네스의 체)

boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i <= N; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= N; j += i) {
            isPrime[j] = false;
        }
    }
}

i * i부터 지우는 이유는, 그 이전의 배수들은 이미 이전 단계에서 제거되었기 때문!

2️⃣ 소수 리스트 생성

List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= N; i++) {
    if (isPrime[i]) primes.add(i);
}

3️⃣ 투 포인터로 연속된 소수의 합 탐색

int left = 0, right = 0, sum = 0, answer = 0;

while (true) {
    if (sum >= N) {
        if (sum == N) answer++;
        sum -= primes.get(left++);  // 왼쪽 포인터 이동
    } else {
        if (right == primes.size()) break;  // 오른쪽 끝까지 탐색 완료
        sum += primes.get(right++);         // 오른쪽 포인터 확장
    }
}

sum >= N이면 왼쪽 포인터를 이동시켜 합을 줄인다.

sum < N이면 오른쪽 포인터를 이동시켜 합을 늘린다.

합이 정확히 N일 때마다 answer를 1 증가시킨다.

시간 복잡도는 O(N) 수준.

---

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_1644_소수의연속합_G3 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int answer = 0;

        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i)
                    isPrime[j] = false;
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= N; i++)
            if (isPrime[i]) primes.add(i);

        int left = 0, right = 0, sum = 0;

        while (true) {
            if (sum >= N) {
                if (sum == N) answer++;
                sum -= primes.get(left++);
            } else {
                if (right == primes.size()) break;
                sum += primes.get(right++);
            }
        }

        System.out.println(answer);
    }
}