🧩 Baekjoon 2581 - 소수

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

예제

✅ 입력 1

60
100

✅ 출력 1

620
61

✅ 입력 2

64
65

✅ 출력 2

-1

작성 코드

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

public class Main {
    static int[] primeArr;
    
    public static void main(String[] args) throws IOException {
        // 1. 변수 선언 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        int result = 0;
        int minValue = 0;
        
        // 2. 처리
        makePrimeArr(n);
        
        for (int i = m; i <= n; i++) {
            if (primeArr[i] == 1) {
                result += i;
                if (minValue == 0) minValue = i;
            }
        }
        
        // 3. 출력
        if (result == 0) {
            System.out.println(-1);
        } else {
            System.out.println(result);
            System.out.println(minValue);
        }
    }
    
    static void makePrimeArr(int num) {
        // 배열 초기화
        primeArr = new int[num + 1];
        Arrays.fill(primeArr, 1);
        primeArr[0] = primeArr[1] = 0;
        
        // 에라토스테네스의 체
        for (int i = 2; i <= num; i++) {
            if (primeArr[i] == 0) continue;
            for (int j = i * 2; j <= num; j += i) primeArr[j] = 0;
        }
    }
}

회고

• 항상 문제를 풀 때 구체적인 생각 없이 머리로만 예상되는 방법을 그리곤 했는데 가능한 문제를 작게 쪼개려고 해보았으며, 다른 문제를 풀 때에도 이런 방식으로 접근해보고자 한다.
• M이상 N이하의 자연수를 순회하여 소수의 합과 최솟값을 출력하는 메인 로직과 소수를 판별하는 서브 로직 2개로 나누었다.
• 에라토스테네스의 체를 통해 배열 구성은 한 번만 하고 이후에는 활용만 하면 된다는 점을 이해했다.