소수 찾기(에라토스테네스의 체)

일반 방법으로 "소수찾기" 알고리즘 문제를 풀면 시간초과를 경험하는 일이 많기 때문에 에라토스테네스의 체를 이용해서 소수를 구해보자. 

 

1. 2부터 n까지의 모든 수를 나열한다.
2. 2는 소수이므로 소수로 입력한다. 후에 2의 배수들은 소수가 아니게 되므로 n까지의 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 3은 소수이기에 체크하고, 똑같이 3의 배수를 모두 지운다.
4. 다음 소수인 5도 지워지지 않았기에, 5의 배수를 모두 지운다.
5. 위의 과정을 n의 제곱근전의 최대 소수까지 반복을 해준다 (Math.sqrt())를 이용하자.

 

출처 : 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

 

 

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

코딩테스트 연습 - 소수 찾기 | 프로그래머스

위의 문제를 한번 풀어보면서 느껴보자.

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] number = new int[n+1];
 
        //2부터 n까지의 수를 배열에 넣는다.
        for(int i = 2; i <= n; i++) {
            number[i] = i;
        }
 
        //2부터 시작해서 그의 배수들을 0으로 만든다.
        //후에 0이면 넘어가고 아니면 그의 배수들을 다시 0으로 만든다.
        for(int i = 2; i <= n; i++) {
            if(number[i] == 0) continue;
 
            for(int j = 2 * i; j <= n; j += i) {
                number[j] = 0;
            }
        }
 
        //배열에서 0이 아닌 것들의 개수를 세준다.
        for(int i = 0; i < number.length; i++) {
            if(number[i] != 0) {
                answer++;
            }
        }
        return answer;
    }
}

 

 

[출처] 코드 + 내용

https://ju-nam2.tistory.com/19

[Java][프로그래머스][Level 1] 소수 찾기 - 3가지 방법 이용