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

*20230113 의 회고

 

 

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

프로그래머스

 

   오늘 알고리즘 문제를 풀다가, 소수를 구하는 문제를 마주했다. 'n 이하의 수에서 소수의 개수를 구하시오.' 라는 문제를 만났을 경우, 코테 공부를 어느정도 한 사람이라면 이중 for 문을 이용해서 구하면 되겠다는 생각은 쉽게 할 수 있을 것이다. 그러나 만약 n의 값이 매우 큰 수가 주어진다면? 무조건 시간초과로 문제풀이에 실패할 것이다. 보통 이 문제는 에라토스테네스의 체를 이용해서 문제를 풀 수 있는가를 따지는 문제다. 현존하는 소수 구하는 방법론에서는 에라토스테네스의 체를 이용한 방법이 제일 빠르다고 한다.

 

   에라토스테네스의 체에 관한 설명은 위키백과를 첨부하겠다.

 

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

 

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

 

 

   이를 이용한 나의 첫번째 풀이는 이렇다.

 

class Solution {
   public int solution(int n) {
        int answer = 0;
        int[] arr = new int[n+1]; //index 값으로 연산을 하기 위해 n+1 까지의 배열을 선언
        for(int i = 2; i < n + 1; i++) {
        	if (arr[i] = 0) {
            	answer++;
            	arr[i] = 1; // 2, 3, 5, 7 등의 소수는 처음에 0 이므로 갯수를 카운트 해주고 1로 바꿔줌
            }
            for(int j = i; j < n + 1; j = j + i) { //2부터 n까지 2의 배수, 3의 배수..i의 배수 부분의 인덱스에 해당하는 값 1로 설정
                arr[j] = 1;
            }
        }
        for(int i = 2; i < arr.length; i++) {
            if (arr[i] == 0){ // 2, 3, 5, 7 ... 등으로도 나눠지지 않는 소수의 갯수를 카운트
            answer++;
            }
        }
        return answer;
    }
}

 

   위의 코드로 실행을 하게되면, 아래와 같은 결과가 나온다.

 

 

   그런데, 에라토스테네스의 성질 중 예를 들어 120 보다 작은 수 중에 소수를 구하기 위해서는 11^2 > 120 이므로, 11 보다 작은 수의 배수만 지워도 값을 구할 수 있다. 따라서 위의 코드를 수정하면 아래와 같다.

 

class Solution {
 public static int solution(int n) {
        int answer = 0;
        int[] arr = new int[n+1];
        for(int i = 2; i * i < n + 1; i++) { // i의 범위를 변경해줌
            if(arr[i] == 0) {
                answer++;
                arr[i] = 1;
            }
            for(int j = i * i; j < n + 1; j = j + i) { //에라토스테네스 체의 특징과 같은 맥락으로, i*i 미만은 이미 처리되었으므로 j의 시작값을 i*i 로 최적화 할 수 있다.
                arr[j] = 1;
            }
        }
        for(int i = 2; i < arr.length; i++) {
            if (arr[i] == 0){
                answer++;
            }
        }
        return answer;
    }
}

 

   실행 결과가 확실히 줄어든 것을 볼 수 있다.

 

 

 

 

   오랜만에 고등학교 때로 돌아가서 수학공부를 한 기분이 든다...ㅋㅋ 까먹지 않도록 복습을 잘 해둬야겠다! 항상 알고리즘은 시간 복잡도를 어떻게 하면 줄일 수 있을 지에 대해 고민하도록 하자!