class Solution {

    /*DP shit again
    public boolean isPrime(int n) {
        if (n <= 1)
            return false;
 
        if (n == 2 || n == 3)
            return true;
 
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i <= Math.sqrt(n); i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
    public int countPrimes(int n) {
        if (n-1 <= 1) return 0;
        int[] result = new int[n];
        for (int i=2; i<=n-1; i++) {
            result[i] = result[i - 1];
            if (isPrime(i)) {
                result[i]++;
            }
        }
        return result[n-1];
    }
    */

    // Sieve of Eratosthenes
    public static int countPrimes(int n) {
        if (n <= 2) return 0;
        boolean[] isPrime = new boolean[n];
        for (int i=3; i<n; i+=2) {
            isPrime[i] = true;
        }
        isPrime[2] = true;
        for (int i=3; i<Math.sqrt(n); i+=2) {
            if (isPrime[i]) { // if i is prime
                for (int j=i*i; j<n; j+=i*2) { // mark i*i, i*(i+1), i*(i+2),... as non-prime
                    isPrime[j] = false;
                }
            }
        }
        int result = 0;
        for (int i=2; i<n; i++) {
            if (isPrime[i]) result++;
        }
        return result;
    }
}