소수 찾기 (프로그래머스) - Java

해결 방법

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i = 2; i <= n; ++i) {
            boolean isPrime = true;
            for(int j = 2; j < i; ++j) {
                if(i % j == 0) {
                    isPrime = false;   
                    break;
                }
            }
            if(isPrime) ++answer;
        }
        return answer;
    }
}

만약 위와 같은 방법의 코드로 풀게 된다면 효율성에서 실패하게 된다. 2중 for문으로 시간복잡도가 O(N^2)이다.

 

이 문제를 풀기 위해서는 에라토스테네스의 체에 대해서 알아야 한다.

에라토스테네스의 체

 

구현 코드는 다음과 같다.

import java.lang.Math;

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] arr = new boolean[n + 1];
       
        // 모두 true로 초기화한다.
        for(int i = 2; i <= n; ++i)
            arr[i] = true;
        
        // 소수가 아닌 숫자를 제외할
        // 배열의 최대 범위를 구한다.
        int limit = (int)Math.ceil(Math.sqrt(n));  
        
        // 2 ~ (제거할 배수) 범위까지 반복하며
        // 그 배수에 해당하는 수를 제외한다.
        for(int i = 2; i <= limit; ++i)
        {
            if(arr[i]) {
                for(int j = i * i; j <= n; j += i)
                    arr[j] = false;    
            }
        }
        
        // 소수의 갯수를 세준다.
        for(int i = 2; i <= n; ++i) 
            if(arr[i]) ++answer;
            
        return answer;
    }
}