[백준] 1644번 : 소수의 연속합 - JAVA [자바]

 

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

---

📝 문제 설명

자연수 N을 입력받으면 이를 연속된 소수의 합으로 나타내는 수들의 경우의 수를 출력하면 된다.

✨ 제출 코드

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

public class Main {
    static List<Integer> prime = new ArrayList<>();

    public static void isPrime(int num){
        int [] temp = new int[num+1];

        for(int i = 2; i <= num; i++){
            temp[i] = i;
        }

        for(int i = 2; i <= Math.sqrt(num); i++){
            if(temp[i] != 0){ //temp[i]는 소수
                for(int j = i+i; j <= num; j+=i){ //소수의 배수들 제거
                    temp[j] = 0;
                }
            }
        }

        for(int i = 2; i <= num; i++){
            if(temp[i] != 0) prime.add(temp[i]);
        }
    }

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

        isPrime(N);

        for(int rt = 0; rt < prime.size(); rt ++){
            sum += prime.get(rt);

            if(sum == N){
                answer ++;
            }
            while( sum >= N){
                sum -= prime.get(lt);
                lt++;

                if(sum == N){
                    answer ++;
                }
            }
        }

        System.out.println(answer);
    }
}

 

✌️ 코드 설명

먼저 입력받은 자연수에 대해서 에라토스테네스의 체를 통해 소수만 리스트에 넣어주었다.

그리고 투 포인터를 이용해 rt를 증가시키면서 값을 더하면서 입력받은 수 와 체크하고 맞으면 answer증가 합이 입력받은 수보다 크면 lt 빼주고 입력받은 수와 체크 이 과정을 반복했다.

 

♨️ 마무리

 

🔎 에라토스테네스의 체(Sieve of Eratosthenes)란?

에라토스테네스의 체는 주어진 범위 내의 모든 소수를 빠르게 찾는 알고리즘입니다.
이 방법은 배수를 제거하는 방식을 사용하여 시간 복잡도가 O(N log log N)으로 매우 효율적입니다.

---

🛠 알고리즘 동작 원리

1. 2부터 시작해서 특정 숫자의 배수를 모두 제거합니다. (2의 배수, 3의 배수, 5의 배수 등…)
2. 이미 지워진 숫자는 소수가 아니므로 건너뜁니다.
3. 이 과정을 √N까지 반복하면 남아 있는 숫자들이 소수입니다.

숫자	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
초기	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔	✔
2의 배수 제거	✔	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌	✔	❌
3의 배수 제거	✔	✔	❌	✔	❌	✔	❌	❌	❌	✔	❌	✔	❌	❌	❌	✔	❌	✔	❌	❌	❌	✔	❌	❌	❌	❌	❌	✔	❌
5의 배수 제거	✔	✔	❌	✔	❌	✔	❌	❌	❌	✔	❌	✔	❌	❌	❌	✔	❌	✔	❌	❌	❌	✔	❌	❌	❌	❌	❌	✔	❌

 

📊 시간 복잡도 분석

• O(N log log N) → 매우 효율적!
• 소수를 하나씩 판별하는 O(N√N)보다 훨씬 빠름.
• j = i * i에서 시작해 불필요한 중복 제거 → 더 빠르게 실행됨.

---

🎯 정리

• 배수들을 한 번에 제거해서 빠름.
• O(N log log N)으로 매우 효율적.
• 소수를 구하는 가장 기본적이고 강력한 방법.