[알고리즘 공부] 소수 구하기 (에라토스테네스 체)

 

 

 

class Solution {
    public int solution(int n) {
        
        // 1 ~ n까지 값을 넣을 배열 생성
        int[] arr = new int[n+1];
        
        // 배열 인덱스에 인덱스값 할당 
        for(int i=0; i<=n; i++)
            arr[i] = i;
        
        // 소수가 아닐 경우 배열의 요소 값을 0으로 할 것이다.
        arr[1] = 0;
        
        // 소수가 아닌 수의 개수를 세어줄 수
        int count = 0;
        
        for(int i=1; i<=n; i++) {
            if(arr[i] == 0) {  // 소수가 아닐 경우
                count++;
                continue;
            }

            // 배수를 활용하여 소수가 아닌 수를 0으로 할당
            for(int k=2; k<=n/i; k++) // 본인은 제외하기 위해 k는 2부터 시작
                arr[i*k] = 0;
            
        }  // end of for
        
        return n-count;
    }
}