BOJ 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. 정보

   • 자연수 $N (1 \le N \le 4000000)$

2. 목표

   • 자연수 N이 주어졌을떄, 해당 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수 구하기

3. 제약 조건

   • 한 소수는 한 번만 덧셈에 사용뒬 수 있다. 즉, 두번 이상 사용하면 안됨
   • 반드시 연속된 소수의 합으로 나타내야 한다.

풀이

1. 알고리즘

   • 에라토스테네스의 체
     • 1부터 N까지 해당 알고리즘을 사용하여 소수인지 처리한다.
   • 투 포인터 활용
     • 구한 소수들을 이용해 연속된 소수의 합으로 N을 표현할 수 있는 경우의 수 계산

2. 탐색 과정

   1. 에라토스테네스의 체를 이용하여 1부터 N까지 소수 판별을 한다
   2. 투 포인터를 활용하여 경우의 수를 구한다
      • start, end를 선언
        • start는 시작, end는 끝을 의미
      • current_sum이 N보다 작으면 end를 증가시킴
      • current_sum이 N보다 크면 start를 증가시킴
      • current_sum이 N과 같다면 경우의 수를 증가시키고, N을 증가

3. 종료 조건

   • end가 마지막을 넘어가거나, start가 end와 같아진다면 종료

에라토스테네스의 체

일반적으로 소수를 판별하는 방법은 다음과 같다.

• 소수는 자기 자신과 1만 약수로 가진다.
  • N 미만의 숫자 중에서 나머지 연산을 했을 경우, 0이 되면 약수를 가지고 있으므로, 소수가 아니다.
• 따라서 해당 알고리즘을 그대로 실행 한다면, O(N ^ 2)이 되게 된다.
  • 즉 시간이 상당히 오래 걸린다.
    

이를 해결하기 위해 고안된 알고리즘이 에라토스테네스의 체이다.
해당 알고리즘의 원리는 다음과 같다

• 해당 수가 소수라면, 해당 수의 배수들은 모두 해당 수를 약수로 가지고 있으므로, 소수가 되지 못한다.
• 즉
  1. 소수인지 체크하는 배열을 만든다.
  2. 해당 배열 전체를 소수로 초기화 시킨다.
  3. 0과 1은 소수가 아니므로 소수가 아니라고 설정한다.
  4. 2부터 $\sqrt{N}$까지 반복문을 돈다.
     1) 만약 현재 수가 소수라면,
     • 해당 수를 제외한 배수들을 모두 소수가 아니라고 처리한다.
       • 이때 시작점은 i * i부터 시작한다.

여기서 두 가지 의문이 들 수 있겠다.
1. 왜 2부터 N의 제곱근 까지만 반복하지?
2. 왜 배수들을 처리할 때 시작점이 i * i 부터지?

1번의 이유는 다음과 같다.
어떤 수 x가 소수가 아니라면, x는 두 수 a와 b의 곱으로 표현 할 수 있을것이다.

$x = a \times b$

해당 식에서, a와 b중 적어도 하나는 $\sqrt{N}$보다 작거나 같아야 한다.

만약 a > $\sqrt{N}$ 이고 b > $\sqrt{N}$라면, $a \times b > N$이 되어 x가 N보다 커지기 때문이다.
따라서 $\sqrt{N}$이전에 이미 약수들로 인해 소수로 걸러지게 된다.

2번의 이유는 다음과 같다.

이미 걸러진 배수는 처리할 필요가 없다.

• 소수 $i$에 대해 배후를 지울 때
  $i \times 2, i \times 3,...,i \times (i + 1)$는 이미 이전 단계에서 더 작은 소수의 배수로 처리되었다.

예시를 보자면,

• $i = 5$ 일 경우
  2로 처리 된 배수는 10, 15 ,20, ...
  3로 처리 된 배수는 15, 30, 45, ...

따라서 $i = 5$일 경우 $5 \times 2, 5 \times 3,...$는 이미 걸러져 있게 된다.
즉 $5 \times 5$부터 시작해 중복 계산을 피할 수 있게 하는 것이다.

해당 알고리즘의 코드는 다음과 같다.

public void prime(int N){
		list = new ArrayList<>();
        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;
                }
            }
        }
        for (int i = 2; i <= N; i++) {
            if(isPrime[i]) {
                list.add(i);
            }
        }
}

---

코드

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

public class BOJ1644 {

    static int N;
    static boolean[] isPrime;
    static ArrayList<Integer> list = new ArrayList<>();

    private static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
		//에라토스테네스의 체
        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;
                }
            }
        }
        for (int i = 2; i <= N; i++) {
            if(isPrime[i]) {
                list.add(i);
            }
        }

        //투 포인터 활용
        int start = 0, end = 0, current_sum = 0, result = 0;

        while (end < list.size()) {
            if (current_sum < N) {
                current_sum += list.get(end++);
            } else if (current_sum > N) {
                current_sum -= list.get(start++);
            } else{
                result++;
                current_sum += list.get(end++);
            }
        }

        while(current_sum >= N && start < list.size()) {
            if (current_sum == N) {
                result++;
            }
            current_sum -= list.get(start++);
        }
        System.out.println(result);
    }

    public static void main(String[] args) throws IOException {
        BOJ1644.solution();
    }
}