[백준] 2581 소수 - Java

문제

링크

---

코드

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[] primeNumber = new boolean[(N + 1)];
        primeNumber[0] = true;
        primeNumber[1] = true;
        for (int i = 2; i <= Math.sqrt(primeNumber.length); i++) {
            if (primeNumber[i]) continue;
            for (int j = (i * i); j < primeNumber.length; j += i) {
                primeNumber[j] = true;
            }

        }

        int sum = 0;
        int min = -1;
        for (int i = M; i <= N; i++) {
            if (!primeNumber[i]) {
                sum += i;
                if (min == -1) min = i;
            }
        }
        if (sum == 0) {
            System.out.println(-1);
        } else {
            System.out.println(sum);
            System.out.println(min);
        }
    }
}

---

리뷰

연속으로 소수문제가 나왔다.
이전과 같이 풀어도 되지만 소수인지 판별해야되는 수가 크면 비효율적이게 된다.
그래서 여러 방법을 찾아보다가 에라토스테네스의 체라는 방식을 이용해보았다.

이름이 낯설어서 뭔가했는데 일전에 비슷한 방식으로 문제를 풀었던 기억이 있었다.
그 때는 제곱근을 이용하지않았었는데 제곱근 방식도 유용해보여 같이 적용시켜보았다.

왜 소수를 판별할 때 그 수까지가 아닌 제곱근 까지만 판별해도 그 수 가 소수인지 알 수 있을까?

해당 수인 n은 자연수 a, b에 대해 n = a * b로 표현할 수 있다.
또한 n은 자신의 제곱근끼리 곱하는 방식으로 표현이 가능하다.
n = sqrt(n) * sqrt(n)

이는 a * b = sqrt(n) * sqrt(n) 이고 a, b가 자연수이려면
a=b=m 이거나 a>m, b<m 이거나, a<m, b>m 이어야한다.

즉 a, b가 어떠한 수라도 둘 중 하나는 제곱근보다 작아야 하므로 제곱근 까지만 판별하면 그 수가 소수인지 알 수 있다.

처음에는 이해하기가 어려워서 계속 보니 이해가되었다 😅

아무튼 제곱근과 에라토스테네스의 체를 이용해
2를 제외한 2의배수부터 시작해서 제곱근 이하의 값의 배수를 정리함으로 써
소수가 false값을 가진 배열을 만들고 출력 결과에 맞게 합과 최솟값을 출력하도록 구현하였다.