[BOJ/수학] 백준 1644 - 소수의 연속합 (Java)

1644 - 소수의 연속합

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

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다
ex. 3 : 3 (한 가지)/ 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) / 53 : 5+7+11+13+17 = 53 (두 가지)
But, 연속된 소수의 합으로 나타낼 수 X 자연수: 20 : 7+13 -> 7과 13이 연속 X
한 소수는 반드시 한 번의 덧셈에 사용될 수 있음 -> 3+5+5+7과 같은 표현 적합 X

입력: 자연수 N (1 <= N <= 4,000,000)
출력: 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수

---

풀이

에라토스테네스의 체

소수가 아닌 수(합성수) 지워나가면서 소수만 남기는 방식

=> 주어진 숫자 N까지 모든 소수 빠르게 찾는 방법 

• 시간복잡도: O(N log log N)
• 2부터 N까지 모든 수 나열
• 2를 제외한 2의 배수 지움(2는 소수)
• 남아있는 수 중 다음 수를 제외한 그 수의 배수 지움
  • ex. 3을 제외한 3의 배수 지움

=> 반복

 

• 2부터 N까지의 소수를 `arr` 리스트에 저장

List<Integer> arr = new ArrayList<>();
for (int i = 2; i <= N; i++) {
    if (!isNotPrime[i]) {
        arr.add(i);
        for (int j = i * 2; j <= N; j += i) {
            isNotPrime[j] = true;
        }
    }
}

 

• 투 포인터(슬라이딩 윈도우)로 연속합 구함
  • 시작 포인터: `p1`, 끝 포인터: `p2` (`arr`의 인덱스)
  • `sum >= N` -> `p1`을 줄여서 합 줄이기
  • `sum < N` -> `p2`을 늘려서 합 늘리기
  • `p2 == arr.size()`: 더 이상 오른쪽으로 갈 수 X -> `break`
  • 합이 정확히 N이 되었을 때만 `cnt++`

int p1 = 0, p2 = 0;
int sum = 0;
int cnt = 0;
while (true) {
    if (sum >= N) sum -= arr.get(p1++);
    else if (p2 == arr.size()) break;
    else sum += arr.get(p2++);

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

---

코드

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

// 소수의 연속합
public class boj_1644 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        boolean[] isNotPrime = new boolean[N + 1];

        List<Integer> arr = new ArrayList<>();
        for (int i = 2; i <= N; i++) {
            if (!isNotPrime[i]) {
                arr.add(i);
                for (int j = i * 2; j <= N; j += i) {
                    isNotPrime[j] = true;
                }
            }
        }

        int p1 = 0, p2 = 0;
        int sum = 0;
        int cnt = 0;
        while (true) {
            if (sum >= N) sum -= arr.get(p1++);
            else if (p2 == arr.size()) break;
            else sum += arr.get(p2++);

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

        System.out.println(cnt);
    }
}