[2021-05-05] 소수 찾기

푼 시간 : 30분

언어 : 자바

 

---

 

전에 에라토스테네스의 체 로 풀어야만 한다는 글을 보고

안 풀어놓고 까먹었는데,

 

오늘 다시 보게 됐다..

이해가 안된다면 알고리즘 항목에 있는 에라토스 테네스의 체를 보면

금방 이해가 되실 것 같다.

 

import java.util.*;

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

        int[] filter = new int[n + 1];
        Arrays.fill(filter, 1);
        // 필터에 1을 채운다.
        filter[0] = 0;
        filter[1] = 0;
        // 0과 1은 소수가 아님을 미리 필터링 한다.

        for (int i = 2; i < Math.sqrt(n) + 1; i++){
        // 제곱근+1의 범위
            if (filter[i] == 1){
                for (int j = i * 2; j <= n; j+=i){
                // 2의 배수를 다 지우고, +1을 해서 또 3의 배수를 지우고,
                +1을 해서 4의 배수를 지우고 ....
                    filter[j] = 0;
                    // 배수는 다 0으로 필터링
                }
            }
        }

        for (int check: filter){
            if (check == 1){
                answer++;
            }
            // 필터에 안걸린 살아남은 1들만이 소수
        }
        
        return answer;
    }
}