백준 2581번: 소수

레곤토르닉·2025년 8월 11일

baekjoon

BaekJoon

목록 보기

22/64

백준 2581번: 소수

주어진 숫자 범위 M과 N 사이에서 소수(prime number)를 모두 찾아, 그 합과 최솟값을 구하는 문제입니다. 소수를 판별하는 방법을 구현하고, 범위 내에서 반복하며 조건을 처리하는 것이 핵심입니다.

✅ 문제 개요

항목	내용
문제 번호	2581번 - 소수
난이도	실버 5
핵심 알고리즘	수학, 정수론, 소수 판정

✅ 문제 설명 요약

입력:
1. 첫째 줄: 자연수 M
2. 둘째 줄: 자연수 N (M ≤ N, N ≤ 10,000)
출력:
1. M 이상 N 이하의 소수들의 합을 첫째 줄에 출력합니다.
2. 그 중 최솟값을 둘째 줄에 출력합니다.
3. 만약 M과 N 사이에 소수가 없을 경우, 첫째 줄에 -1을 출력합니다.
규칙:
- 소수는 1과 자기 자신만으로 나누어지는 1보다 큰 자연수입니다.
- 1은 소수가 아님에 유의해야 합니다.

✅ 풀이 전략

이 문제는 두 단계로 나누어 해결할 수 있습니다. 먼저 '소수를 판별하는 함수'를 만들고, 그 다음 M부터 N까지의 숫자를 반복하며 이 함수를 이용해 소수를 찾아내는 것입니다.

1️⃣ 소수 판별 함수 만들기

어떤 숫자 num이 소수인지 판별하는 방법은 다음과 같습니다.

num이 1이라면 소수가 아니므로 즉시 false를 반환합니다.
2부터 num-1까지의 모든 수로 num을 나누어 봅니다.
만약 한 번이라도 나누어떨어지면, num은 약수를 가진 것이므로 소수가 아닙니다. 즉시 false를 반환합니다.
반복문이 모두 끝날 때까지 나누어떨어지지 않았다면, num은 1과 자기 자신 외에 약수가 없는 것이므로 소수입니다. true를 반환합니다.

// 소수 판별 함수
public static boolean isPrime(int num) {
    if (num < 2) { // 1은 소수가 아님
        return false;
    }
    // 최적화: num의 제곱근까지만 확인
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false; // 다른 수로 나누어 떨어지면 소수가 아님
        }
    }
    return true; // 나누어 떨어지지 않으면 소수
}

2️⃣ 범위 내에서 소수 찾고 계산하기

소수의 합을 저장할 변수 sum과 최솟값을 저장할 변수 min을 초기화합니다. min은 처음 발견된 소수로 설정해야 하므로, 초기값은 충분히 큰 수(또는 -1)로 설정해두는 것이 좋습니다.
for 반복문을 사용하여 M부터 N까지의 모든 숫자를 순회합니다.
각 숫자마다 위에서 만든 isPrime() 함수를 호출하여 소수인지 판별합니다.
만약 소수라면:
- sum에 해당 숫자를 더합니다.
- min 값이 아직 초기값이라면 (즉, 처음 발견된 소수라면), min을 현재 숫자로 설정합니다.

3️⃣ 결과 출력하기

반복문이 모두 끝난 후, sum이 0이라면 (즉, 소수가 하나도 없었다면) -1을 출력합니다.
그렇지 않다면, 계산된 sum과 min을 차례대로 출력합니다.

✅ Java 코드 예제

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {

    // 소수 판별 함수
    public static boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        for (int i = 2; i * i <= num; i++) { // 최적화: num의 제곱근까지만 확인
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        int sum = 0;
        int min = -1;

        for (int i = M; i <= N; i++) {
            if (isPrime(i)) {
                sum += i;
                // min이 -1이라는 것은 아직 첫 소수를 못 찾았다는 의미
                if (min == -1) {
                    min = i;
                }
            }
        }

        if (sum == 0) {
            bw.write("-1");
        } else {
            bw.write(String.valueOf(sum));
            bw.newLine(); // 줄바꿈
            bw.write(String.valueOf(min));
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

⚠️ 실전 주의사항

항목	설명
소수 판별 최적화	어떤 수 `N`의 약수는 그 제곱근(`√N`)을 기준으로 대칭적으로 존재합니다. 따라서 `i`를 2부터 `N-1`까지 전부 확인할 필요 없이, `√N`까지만 확인해도 충분합니다. (`for (int i = 2; i * i <= num; i++)`)
1 처리	1은 소수가 아니라는 점을 명시적으로 처리해야 합니다. `isPrime` 함수 첫 부분에서 `num < 2` 조건을 확인하는 것이 중요합니다.
결과 출력 형식	소수가 없는 경우 `-1` 하나만 출력하고, 있는 경우에는 합과 최솟값을 두 줄에 걸쳐 출력해야 합니다. `bw.newLine()` 사용에 유의하세요.
변수 초기화	합계 `sum`은 0으로, 최솟값 `min`은 첫 소수를 저장하기 위해 -1이나 `Integer.MAX_VALUE` 등으로 초기화하는 것이 편리합니다.

📝 마무리 요약

✔️ 소수 판별 로직을 정확히 구현하는 것이 첫 번째 단계입니다.
✔️ 1은 소수가 아님을 반드시 예외 처리해야 합니다.
✔️ M부터 N까지 반복하며, 소수일 경우 합계와 최솟값을 업데이트합니다.
✔️ 소수가 하나도 없는 경우를 판별하여 -1을 출력하는 로직을 마지막에 추가합니다.