[백준 P1644] 소수의 연속합 Java

P1644 소수의 연속합

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)

20

3

출력값

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

0

1

알고리즘

누적합과 투 포인터 알고리즘을 이용한다. 우선 N이하의 소수들로 이루어진 배열을 만든다. 소수의 배열은 에라토스테네스의 체를 이용한다. 에라토스테네스의 체가 무엇인지 모른다면 아래의 사이트를 참고하자.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

public static void getPrime() {
    for (int i = 2; i <= N; i++) {
        if (isPrime[i] == true) {
            int current = i + i;
            while (current <= N) {
                isPrime[current] = false;
                current += i;
            }
        }
    }
}

그 다음 소수의 합을 누적하여 누적합 배열을 만든다. 예를 들어 9 이하의 소수 배열을 누적합 처리 한다고 가정해보자. 9 이하의 소수는 2 3 5 7이다. 이를 배열로 만들면 [2, 3, 5, 7] 이 되고, 누적합 배열로 만들면 [2, 5, 10, 17]이 된다.

각 배열의 원소가 나타내는 의미는 다음과 같다.

 

[2, 5, 10, 17]

2 = 2

5 = 2 + 3

10 = 2 + 3 + 5

17 = 2 + 3 + 5 + 7

 

이제 start와 end포인터를 선언하고 각각 0과 1을 가리킨다. 누적합 배열을 이용하여 두 구간의 차이를 계산한다. start가 1, end가 3이라 가정하자. 누적합 배열[end] - 누적합 배열[start]를 통해 8(10 - 2)를 얻을 수 있다. 8은 2 + 3 + 5 - 2 와 같으며 이는 구해뒀던 소수 [2, 3, 5, 7] 중 2번째와 3번째 소수를 더한 값과 같다.

즉 start와 end를 적절히 조절하여 빼면 연속된 소수의 합을 쉽고 빠르게 구할 수 있다. start와 end는 아래 조건에 맞추어 조절한다.

1. 누적합 배열을 이용해서 두 구간의 차를 계산하고 만약 두 구간의 차가 N 과 같다면 정답을 1 상승 시키고 start를 1 증가한다.
2. 두 구간의 차가 N 보다 작다면 더 큰 숫자가 더해져야 하므로 end 를 1 증가한다.
3. 두 구간의 차가 N 보다 크다면 더 작은 숫자가 빼져야 하므로 start를 1 증가한다.

 

전체 코드는 아래와 같다.

 

코드

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

public class Main {
    static int N, M;
    static boolean[] isPrime;
    static int[] prime;
    static int answer;

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

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

        getPrime();

        for (int i = 2; i <= N; i++) {
            if (isPrime[i] == true) M++;
        }

        prime = new int[M + 1];
        int cnt = 1;
        for (int i = 2; i <= N; i++) {
            if (isPrime[i] == true) {
                prime[cnt] = i + prime[cnt - 1];
                cnt++;
            }
        }
        
        int start = 0, end = 1;
        while (start <= M && end <= M && start < end) {
            int current = prime[end] - prime[start];

            if (current == N) {
                answer++;
            }
            if (current >= N) {
                start++;
            } else {
                end++;
            }
        }

        System.out.println(answer);
    }

    public static void getPrime() {
        for (int i = 2; i <= N; i++) {
            if (isPrime[i] == true) {
                int current = i + i;
                while (current <= N) {
                    isPrime[current] = false;
                    current += i;
                }
            }
        }
    }
}