BOJ_2581 : 소수

👉 문제링크

2581번: 소수

---

---

🔸 문제 분석 🔸

• m과 n 사이의 소수들의 합과 최소값을 출력한다.

🔸 코드 🔸

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

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

        boolean prime[] = new boolean[n+1];
        prime[1] = true;
        for (int i = 2; i <= n; i++) {
            int c = 1;
            if (!prime[i*c++]) {
                while (i*c <= n) {
                    prime[i*c++] = true;
                }
            }
        }

        long sum = 0;
        int min = 0;
        for (int i = m; i <= n; i++){
            if (!prime[i]) {
                sum += i;
                if (min == 0) min = i;
            }
        }
        if (min == 0) System.out.println(-1);
        else System.out.println(sum + "\n" + min);
    }
}

🔸 코드 해석 🔸

• m과 n을 입력받고, n까지의 소수를 계산한다.
  • boolean 배열 prime을 선언해 i를 2부터 n까지 증가시키며 계산한다.
  • i의 곱은 i가 약수가 되므로 소수가 아니기 때문에 배열 prime에 true값을 저장한다.
  • prime[0]은 사용하지 않고, prime[1]은 1이 약수가 아니기 때문에 따로 true값을 저장한다.
• 배열 prime의 m~n 범위를 순회하며 합과 최소값을 계산해 출력한다.

---

🔸 end 🔸

• 오랜만에 소수 관련 문제를 풀어봤는데, 조금 코드 수정을 해가며 소수 계산을 했지만 원리를 알고 있으니 금방 답을 찾을 수 있었다.
• 틀렸습니다가 나와서 반례를 찾기위해 0/0 , 1/10,000 을 넣어보다가 prime[1]이 true가 안되어 있어서 오류가 나는걸 찾아냈다.