[2581] 소수

난이도: ★★★☆☆ • solved on: 2025-07-15

---

문제 요약

• 문제 유형: 수학, 브루트포스, 소수 판별
• 요구사항: 주어진 M이상 N이하의 소수를 모두 찾아 합(sum)과 최솟값을 출력해야 한다. 소수가 하나도 없으면 -1을 출력해야 한다.

---

사용 개념

1. 자료구조

   • boolean[] : 에라토스테네스의 체(Sieve of Eratosthenes)용 배열

2. 알고리즘/기법

   • 에라토스테네스의 체

3. 핵심 키워드

   • 소수(prime), 범위(range), 제곱근 최적화

---

풀이 아이디어

1. 문제 분해
   • [2, N] 범위 내 소수 여부를 sieve 배열에 표시한다.
   • sieve[0], sieve[1]은 false로 미리 처리한다.
2. 핵심 로직 흐름

// 1) sieve 초기화
boolean[] sieve = new boolean[N+1];
Arrays.fill(sieve, true);
sieve[0] = false;
sieve[1] = false;
// 2) 에라토스테네스의 체 적용
int limit = (int)Math.sqrt(N);
for (int i = 2; i <= limit; i++) {
    if (sieve[i]) {
        for (int j = i * i; j <= N; j += i) {
            sieve[j] = false;
        }
    }
}
// 3) M부터 N까지 순회하며 합(sum)과 최솟값(min) 계산
int sum = 0, min = Integer.MAX_VALUE;
for (int i = Math.max(M, 2); i <= N; i++) {
    if (sieve[i]) {
        sum += i;
        min = Math.min(min, i);
    }
}

3. 예외 처리
   • M이 1 이하일 경우 Math.max(M, 2)로 처리하여 2부터 시작
   • 소수가 하나도 없으면 (sum == 0) -1만 출력

---

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        int sum = 0;
        int min = n;
        boolean[] sieve = new boolean[n+1];
        Arrays.fill(sieve, true);
        sieve[0] = sieve[1] = false;
        for(int i=2;i<=Math.sqrt(n);i++){
            if(sieve[i]){
                for(int j=i*i;j<=n;j+=i){
                    sieve[j] = false;
                }
            }
        }

        for(int i=Math.max(2, m);i<=n;i++){
            if(sieve[i]){
                sum += i;
                if(i < min){
                    min = i;
                }
            }
        }
        if(sum==0){
            System.out.print(-1);
        } else {
            System.out.print(sum + "\n"+min);
        }
    }

---

시간·공간 복잡도

• 시간 복잡도: O(N log log N) (체 생성) + O(N) (결과 계산) → 대략 O(N log log N)
• 공간 복잡도: O(N)

---

어려웠던 점

• M이 1일 때 2부터 시작하도록 처리하는 걸 처음에는 하지 않아 코드가 불안정하게 작동했다.

---

배운 점 및 팁

• Math.sqrt(N)는 반복마다 호출하지 않고 변수에 저장하여 사용하면 성능이 향상된다.
• sieve 배열 크기를 N+1로 선언해야 0부터 N까지 저장이 가능하다.

---

참고 및 링크

• 문제 링크: https://www.acmicpc.net/problem/2581
• 참고 블로그/깃허브: 없음

---

추가 연습 문제

• 비슷한 유형 (GPT 추천): [1929] 소수 구하기'

• 확장 문제 (GPT 추천): 구간 분할 세그먼티드 체(segmented sieve) 구현