[Algorithm] 백준_소수의 연속합_1644번 (JAVA) 에라토스테네스의 체

📝문제

문제

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

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

---

💡풀이

문제 유형

에라토스테네스의 체

투포인터

 

걸린 시간

70분

 

시간 복잡도

O(N * log log N)

 

풀이 방법 도출

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 에라토스테네스의 체 동작 원리
   어떤 수 i가 소수일 때, 그 배수들은 모두 소수가 아니다.
   i가 소수로 판별되면 i의 배수들을 전부 지워간다.
2. i*i부터 지워가는 이유 => i 이전의 수를 이미 검사했기 때문에, 예를 들어 i = 5 라면 5*1, 5*2, 5*3, 5*4는 i가 1,2,3,4 일때 이미 지워진 수 이므로 불필요한 반복을 막기 위해 i*i부터 검사한다.
3. 소수 리스트를 구했다면 투포인터 알고리즘을 사용하여 소수의 합이 N이 될 때를 카운트해준다.

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

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

        ArrayList<Integer> primeList = new ArrayList<>();

        boolean[] prime = new boolean[N+1];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        for(int i = 2; i*i <= N; i++){
            if(prime[i]){
                for(int j = i*i; j <= N; j+=i){//불필요한 반복을 막음
                    prime[j] = false;
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            if (prime[i]) {
                primeList.add(i);
            }
        }

        int left = 0;
        int right = 0;
        int sum = primeList.isEmpty() ? 0 : primeList.get(0);
        int count = 0;
        while (left <= right) {
            if (sum <= N) {
                if (sum == N) {
                    count++;
                }
                right++;
                if (right >= primeList.size()) {
                    break;
                }
                sum += primeList.get(right);

            } else {
                sum -= primeList.get(left);
                left++;
            }
        }

        System.out.println(count);
    }
}

 

처음엔 에라토스테네스의 체를 사용하지 않고 일반적인 소수 구하는 로직을 사용했다, 두 풀이의 시간에 확연한 차이가 있었다.

1. 에라토스테네스의 체 사용

2. 무지성으로 소수 구하기

---

🤔Review

소수 구하기 => 에라토스테네스의 체! 까먹지 말아야지