204. Count Primes

Attempt 1: TIme LImit Exceeded

class Solution {
    public int countPrimes(int n) {
        Set<Integer> primes = new HashSet<Integer>();
        
        if (n <= 2) {
            return 0;
        }
        int num = 1;
        primes.add(2);
        
        for (int i = 3; i < n; i++) {
            int not = 0;
            for (int k : primes) {
                if (i % k == 0) {
                    not++;
                }
            }
            
            if (not == 0) {
                primes.add(i);
                num++;
            }
            
        }
        
        return num;
    }
}

Boolean table이 훨씬 빠르다는 것을 깨달음

class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (notPrime[i] == false) {
                count++;
                for (int j = 2; i*j < n; j++) {
                    notPrime[i*j] = true;
                }
            }
        }
        
        return count;
    }
}