프로그래머스 소수 찾기

문제

programmers.co.kr/learn/courses/30/lessons/12921

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

풀이

에라토스테네스의 체 를 이용하여 소수를 구하였습니다.

"어떤 수의 배수는 소수가 아니다" 라는 내용에 기반하여

현재 수의 배수를 모두 지워나가는 방식입니다.

n까지 배수를 모두 지우는 방식으로 반복해주면 됩니다.

 

일반적인 방법보다 시간이 훨씬 빠르다는 장점이 있습니다.

 

 

 

 

 

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

        int[] arr = new int[n + 1]; //0 : 소수O , 1 : 소수X

        arr[0] = 1;
        arr[1] = 1;

        for (int i = 2; i <= n; ++i) {
            if (arr[i] == 1) continue;
            for (int j = i + i; j <= n; j += i) {
                arr[j] = 1;
            }
        }

        for (int i = 0; i < n + 1; ++i) {
            if (arr[i] == 0) ++answer;
        }

        return answer;
    }
}