[프로그래머스, 12921] 소수 찾기 (java)

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

프로그래머스

728x90

---

메모리: 54.7 MB, 시간: 14.37 ms

사용 알고리즘: 구현

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // 소수가 아닌 것을 표시하는 배열
        boolean[] isNotPrimeNumber = new boolean[n + 1];
        
        for(int i = 2; i <= n; i++) {
            if(!isNotPrimeNumber[i]) {
                
                answer ++;
                
                // i가 소수일 때, i의 배수들은 소수가 아님
                for(int j = 2 * i; j <= n; j += i) isNotPrimeNumber[j] = true;
            }
        }
        
        return answer;
    }
}