[JAVA] 소수 찾기 - 에라토스테네스의 체

문제에 대해서는 여기를 클릭하여 가면 된다.

 

이번에 프로그래머스를 풀면서 에라토스테네스의 체를 사용하여

이 알고리즘을 설명하는 김에 문제풀이도 같이하려 가지고 왔다.

 

일단 에라토스테네스의 체라는 알고리즘부터 알아보자.

에라토스테네스의 체 원리

위 이미지가 에라토스테네스의 체이다.

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

 

위와 같은 방식으로 작동한다. 

말로 해서는 아마 이해하기가 좀 어려울 거다.

 

그러니 코드로 구현해 보자.

코드 및 해설

public int solution(int n){

        int[] prime = new int[n + 1];
        int answer = 0;

		//소수가 아니라면 0, 0과 1은 소수가 아니므로 0
        prime[0] = prime[1] = 0;

        for(int i = 2; i <=n; i++) prime[i] = i; //2부터 소수를 구하고자 하는 구간의 모든 수 나열

        for(int i = 2; i < n;i++){
            if(prime[i] == 0) continue; //소수가 아니라면 continue
            for(int j = 2*i; j <=n; j+=i) prime[j] = 0; //소수의 배수는 소수를 약수로 가지므로 제외
        }

		//소수 개수 구하기
        for(int i = 0; i <prime.length; i++)
            if (prime[i] != 0) answer++;

        return answer;
    }

위의 코드는 에라토스테네스의 체를 이용해 소수의 개수를 구하는 코드이다.

이번 프로그래머스 문제의 답이기도 하다.

 

먼저 int형 배열에 크기를 n+1로 잡는다.

그다음 prime(배열)에 2부터 n까지의 수를 집어넣어준다. (에라토스테네스의 체 원리 1번)

 

for을 돌리면서 소수이면 for을 또 돌려 그 소수의 배수들을 모두 제외해준다. (에라토스테네스의 체 원리 2 ~9)

 

그러면 남은 숫자들이 배열에 남을 것인데,

마지막 for문을 돌려 0이 아니라면(소수라면) answer를 더해준다.

 

이렇게 에라토스테네스의 체를 알아보는 김에 프로그래머스 문제 소수 찾기를 풀어보았다.