프로그래머스 [Lv1. 소수찾기]_ 에라토스테네스의 체

수정 전 코드:

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i=2;i<=n;i++){
            if(isPrime(i)) answer++;
        }
        return answer;
    }
    
    public boolean isPrime(int n){
        boolean result = true;  //소수이다
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0) result = false;  //소수가 아니다
        }
        return result;
    }
}

정확성 75점 효율성 0점

 

소수 찾기 문제에선, 에라토스테네스의 체 알고리즘을 이용해 효율적으로 소수를 찾을 수 있다.

에라토스테네스의 체란, "소수가 되는 수의 배수를 지우면 남는 건 소수가 된다"라고 생각하면 된다.

1. 2는 소수이니 체크, 2의 배수를 지워준다.

2. 3은 소수이니 체크, 3의 배수를 지워준다. 

3. 5는 소수이니 체크, 5의 배수를 지워준다.

위의 과정을 계속 반복하여 남는 수는 모두 소수가 된다는 것이다.

 

(출처: 위키백과)

에라토스테네스의 체

짤을 보면서 정리해보자면,

2부터 120까지의 소수를 찾는다고 했을 때, 

120의 제곱근보다 작은 소수(=2,3,5,7)의 배수들을 모두 지우고 남은 수들이 소수가 된다는 것입니다.

 

이 알고리즘을 토대로 [소수찾기] 문제를 수정보면, 

package lv1;

import java.util.ArrayList;

public class 소수찾기 {
    public static void main(String[] args) {
        System.out.println(solution(10));
    }
    public static int solution(int n){
        int answer = 0;
        ArrayList<Integer> primeList = new ArrayList<>(n+1);

        primeList.add(0);
        primeList.add(0);  //0과 1은 소수 아님으로 처리

        //2부터 n까지는 소수로 처리
        for(int i=2;i<=n;i++){
            primeList.add(1);
        }

        for(int i=2;i*i<=n;i++){  //n의 제곱근보다 작은 소수까지 판별
            if(primeList.get(i) == 1)  //소수라면,
                for(int j=i*i;j<=n;j+=i) primeList.set(j,0); //소수의 배수를 지운다 (i*i 미만은 이미 처리되었으므로, j의 시작값은 i*i로 최적화할 수 있다.)
        }

        for(int i=0;i<=n;i++){
            if(primeList.get(i) == 1) answer++;
        }
        return answer;
    }
}

 

 

정확성과 효율성 모두 만점이 되는 것을 확인했다.

수정 전 코드와 비교해보자면,

수정 전 코드는 2부터 n까지 소수인지 아닌지 하나하나 판별하였다.

에라토스테네스의 체 알고리즘을 적용해 수정 한 코드는 n의 제곱근 보다 작은 소수까지 판별하면 되기에 훨씬 효율적이다.