PROGRAMMERES Level 1 연습문제 소수 찾기 (JAVA 자바)

import java.util.*;

class Solution {  
    public int solution(int n) {
        int answer = 0;
        
        boolean arr[] = new boolean[n+1];
        Arrays.fill(arr, true);
        arr[0] = arr[1] = false;
        
        // 에라토스 테네스의 체
        for(int i=2; i<=Math.sqrt(n); i++){
            if(arr[i]) {
                int j=2;
                while(i*j<=n){
                    arr[i*j] = false;
                    j += 1;
                }
            }
        }
        
        for(int i=2; i<=n; i++) {
    		if(arr[i]) answer++;
    	}

        
        return answer;
    }
}

에라토스테네스의 체 알고리즘을 이용하였다.

boolean 배열을 선언 후 전부 true로 초기화 시켜주고 0과 1은 소수가 아니기 때문에 arr[0], arr[1]을 false로 초기화 해준다.

그 후 2부터 n의 제곱근까지 돌리면서 arr[2]는 true이기 때문에 조건문에 부합하고 2의 배수는 소수가 아니기 때문에 j를 늘려가면서 false 로 초기화해준다. 이때 j를 2로 초기화시킨 이유는 2, 3, 5, 7 ... 은 소수이기 때문에 제외시켜야 하기 때문이다.

그리고 for문을 돌려서 arr[i] 값이 참(소수)일 경 우 answer를 증가시킨다.