[Programmers]소수찾기(난이도:★★★★★)

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

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

class Solution {
    public int solution(int n) {
        return findPrimeCount(n);
    }
    
    public int findPrimeCount(int n){
        int count = 0;
        int[] arry = new int[n];
        // 배열 1 ,2 ,3 ,4 ... n 만들기
        for(int i = 0; i < n; i++){
            arry[i] = i+1;       
        }
        // 해당 숫자가 소수인지 검사
        // 에라토스테네스의 체 알고리즘 사용
        for(int i = 1 ; i < arry.length; i++){
            if(arry[i] != 0){
                count++;
                for(int j = i+arry[i]; j < arry.length; j = j + arry[i]){
                    arry[j] = 0;
                }
                
            }
        }
        return count;
    }
}