[プログラマレベル1]小数点以下の問題解決

に質問

せいげんじょうけん

🖨️ I/O例

エラトステネスのふるい

進行方法

1. 1차원 배열 생성 (n+1 크기)
2. 2부터 배수들을 모두 체크 (단, 자신은 제외하고 4,6,8,10..... <= n)
3. 다음으로 3의 배수들을 모두 체크
4. 4는 아선 2의 배수로써 체크가 되어 소수가 아니기 때문에 PASS
5. ,,,

💡 に答える

class Solution {

    public int solution(int n) {
        int answer = 0;
        // 에라토스테네스의 체로 거르기 위한 배열
        boolean[] flag = new boolean[n + 1];

        // 2부터 n까지의 수들을 지나며
        int i = 1;
        while(1 < ++i && i < n) {

            // 이미 걸러진 수(소수의 배수)는 PASS
            if(flag[i])
                continue;
            
            // 소수의 배수를 체크
            for(int j = i + i; j <= n; j += i)
                flag[j] = true;

        }

        // 걸러지지 않은 수의 개수 구하기
        for(int idx = 2; idx <= n; idx++) {
             if(!flag[idx])
                 answer++;
        }

        return answer;
    }

}

✏️ comment