[JAVA] [프로그래머스] Level 1 - 연습문제 - 소수 찾기

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

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

 

 

 

 

에라토스테네스의 체

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[] tmp = new int[n+1];
        
        // 2부터 n까지의 수를 배열에 넣음
        for(int i=2; i<=n; i++)
            tmp[i] = i;
        
        for(int i=2; i<=n; i++) {
            
            if(tmp[i] == 0)
                continue;
        
            // 배수들을 0으로 만듦
            for(int j=2*i; j<=n; j+=i)
                tmp[j] = 0;
        }
        
        // 0이 아닌 것들의 개수 = 소수의 개수
        for(int i=0; i<tmp.length; i++) {
            if(tmp[i] != 0)
                answer++;
        }
        
        return answer;
    }
}