2021-07-15 / 소수 찾기

문제 설명

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

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

 

제한 조건

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

 

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

입출력 예 #2

1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

초기 코드

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

 

 

정답 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        boolean[] arr = new boolean[n+1];
        
        for (int i=2; i<=n; i++) {
            arr[i] = true;
        }
        
        int num = (int)Math.sqrt(n); //n의 제곱근..?
        
        for (int i=2; i<=num; i++) {
            if (arr[i] == true) {
                for (int j=i; j*i<=n; j++) {
                    arr[i*j] = false;
                }
            }
        }
        
        for (int i=2; i<=n; i++) {
            if (arr[i] == true) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

 

코드 설명

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        boolean[] arr = new boolean[n+1];
        //배열 방의 크기를 n+1로 선언하는 이유는 정수와 배열의 순서를 맞추기 위해서이다. 배열 방 0,1은 사용하지             않는다.

        for (int i=2; i<=n; i++) {
            arr[i] = true;
        }
       

        int num = (int)Math.sqrt(n); 

        //n의 제곱근을 구한다. 반복문이 돌아가는 횟수를 줄여 런타임을 줄인다.
        
        for (int i=2; i<=num; i++) {
            if (arr[i] == true) {

            //false일 경우에는 애초에 보지 않는다. 이미 걸러졌기 때문이다.
                for (int j=i;  j*i<=n;  j++) {

           //체에 거르는 작업이다. i부터 돌리는 이유는 i 앞에 수는 이미 걸러졌기 때문이다. 체에 거르는 수       는 배수 등과 같은 수이다. 
                    arr[i*j] = false;
                }
            }
        }
        
        for (int i=2; i<=n; i++) {
            if (arr[i] == true) {
                answer++;

            //체에 걸러진 친구들은 true 상태이니 카운트한다.
            }
        }
        
        return answer;
    }
}

 

여기서 말하는 체는 에라토스테네스의 소수 찾기 방법을 이용한 것이다. 체에 걸러지는 수들은 각 수들의 배수들이다. 특히 이미 걸러진 수는 다시 거를 필요가 없어 시간이 많이 줄어든다. 

 

 

이 문제에 핵심은 효율성을 최대로 높이기 위해 에라토스테네스의 체를 활용하는 것이다. 참고 링크에 기타 다른 언어들을 사용한 코드 구현이 나와있으니 참고하면 좋을 것 같다.

 

참고 링크 

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

 

 

 

 

 

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