[LeetCode/Java] 204. Count Primes - A012

-  문제

 

-  알고리즘

처음에 항상 소수를 구하는 코드와 비슷하게 짰는데, 시간이 오바되었다고 해서 다시 짰다.

소수를 하나 찾으면 그 소수의 배수를 모두 알아내는 방식으로 진행했다.

 

-  코드

class Solution {
    public int countPrimes(int n) {
        int count = 0;
        int num[] = new int[n+1];
        for(int i = 2; i<n; i++){
            if(num[i] == 0){
                count++;
                for(int j = i; j<n; j += i) num[j] = 1;
            }
        }
        return count;
    }
}