프로그래머스 - 소수 찾기 (에라토테네스의 체)

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

소수란 1과 자기 자신으로만 나누어지는 숫자를 의미합니다.

소수를 찾는 문제이므로 2~N까지 순차적으로 순환하면서 소수를 찾는 소스 코드를 작성했습니다.

첫 번째 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;

        for(int i=2; i<=n; i++){
            boolean check = true;
            for(int j=2; j<i; j++){
                if(i%j == 0){
                    check = false;
                    break;
                }
            }
            if(check)
                answer++;
        }

        return answer;
    }
}

1과 자기 자신 이외에 0으로 나누어지는 숫자를 찾으면 되므로 i% j == 0일 경우 fasle를 대입하도록 했습니다.

그러나 이 코드를 제출하게 되면 마지막 2가지 테스트 케이스를 통과하지 못합니다. 시간 복잡도와 공간 복잡도에서 문제를 일으킵니다.

그래서 에라토테네스의 체를 학습하고 새롭게 소스코드를 작성했습니다.

에라토테네스의 체란?

고대 그리스 수학자 에라토테네스가 발견한 방식으로 위의 보다 훨씬 효과적으로 소수를 찾을 수 있는 방식입니다.

에라로테네스의 체

에라로테네스의 체 알고리즘

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

에라로테네스의 체 풀이

class Solution {
        public int solution(int n) {
            int answer = 0;

            if(n <= 1 ) return 0;

           boolean[] sosu = new boolean[n+1]; // 1. 2~N 만큼의 크기의 표를 만든다.


            for(int i=2; i<= n; i++){ // 2. 만든 표를 ture로 전환한다.
                sosu[i] = true;
            }

            int size = (int) Math.sqrt(n); // 3. 몇의 배수까지 소수의 배수를 체크할지 판단한다.

            for(int i=2; i<=size; i++){ // 4. 2~ size의 배수까지 순환한다.
                if(sosu[i]) 
                    for(int j= i*i; j<=n; j+=i) // 5. 소수라면 자기 자신을 제외하고 다음 배수 ~ N 까지의 배수를 false로 전환한다.
                        sosu[j]=false;
            }

            for(int i=2; i<=n; i++){ // 6. 소수를 체크
                if(sosu[i]) 
                    answer++;
            }


            return answer;
        }
    }

 

출처 : 

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전