Lv1. 소수찾기

▶ 문제

 

▶ 풀이방법

-에라토스테네스의 체를 사용해서 소수판별하여 풀었다.

만약 에라토스테네스의 체를 사용하는 방법을 몰랐다면 어려웠을것 같다...ㅎ

class Solution {
    public int solution(int n) {
        int answer = 0;
        //에라토스테네스의 체(소수 판별)
        int max = 1000000;
        boolean[] arr = new boolean[max];
        for(int i = 2; i < max; i++){
            for(int j = 2*i; j < max; j+=i){
                if(arr[j] == true) continue; 
                arr[j] = true; //소수가 아닌 수들은 true로 값을 바꿔줌.
            }
        }
        
        //입력된 값까지만 판별값 돌림.
        for(int i = 2; i <= n; i++){
            if(!arr[i]) answer++;
        }
        return answer;
    }
}