[Java/자바] 프로그래머스 - 소수 찾기 (에라토스테네스의 체)

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

 

입출력 예

n	result
10	4
5	3

 

---

Solution.java

    public int solution(int n) {
        int answer = 0;
        // 0 ~ n 까지의 수를 가지는 배열 생성
        int[] arr = new int[n + 1];

        // 소수 중 제일 작은 수는 2이므로 2부터 시작한다.
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (arr[i] == 1) {
                continue;
            }
            /*
            i의 배수를 체크하는데 j = i + i 인 이유는
            2 는 소수지만 i가 2 부터 시작하기 때문에 2 가 포함되지 않게 하기 위해서이다.
            j = j + i로 하여 i의 배수를 체크한다.
            */
            for (int j = i + i; j <= n; j += i) {
                arr[j] = 1;
            }
        }
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] != 1) {
                answer++;
            }
        }
        return answer;
    }

 

여기서 반복문을 n의 제곱근까지만 구하도록 한 이유는,

n 이하의 모든 소수를 구한다고 가정했을 시 n은 자연수 a, b에 대해 n = a * b로 표현할 수 있습니다. ( 10 = 2 * 5 or 1 * 10)

그리고 n의 제곱근이 m이라고 한다면 n = m * m이 됩니다.

n = a * b , n = m * m 이 식을 풀어보면 a * b = m * m 이 됩니다.

이 상 태에서 a랑 b가 자연수가 되기 위해선 아래의 3가지 경우 중 한 가지만 가능합니다.

1. a=m 이고 b=m

2. a<m 이고 b>m

3. a>m 이고 b<m

위 경우를 하나로 표현하면 min(a, b) <= m 이 됩니다.

즉, n의 모든 약수에 해당하는 a와 b가 어떠한 약수라도 둘 중 하나는 무조건 m(n의 제곱근) 보다 같거나 작으므로

m까지만 탐색해도 n이 소수인지 알 수 있게 됩니다.

 

 

또한, 이 문제를 통과하기 위해서는 에라토스테네스 체를 사용해야 하는데요

아래의 에라토스테네스에 대한 설명을 보시면서 위 코드 주석을 읽어보시면 이해가 빠를 겁니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

---

참고자료
https://nahwasa.com/entry/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4-%ED%98%B9%EC%9D%80-%EC%86%8C%EC%88%98%ED%8C%90%EC%A0%95-%EC%8B%9C-%EC%A0%9C%EA%B3%B1%EA%B7%BC-%EA%B9%8C%EC%A7%80%EB%A7%8C-%ED%99%95%EC%9D%B8%ED%95%98%EB%A9%B4-%EB%90%98%EB%8A%94-%EC%9D%B4%EC%9C%A0
https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4