@@ -0,0 +1,1094 @@
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * Count the number of prime numbers less than a non-negative number, n.%0A *%0A * Tags: Hash Table, Math%0A * Similar Problems: (E) Ugly Number (M) Ugly Number II (M) Perfect Squares%0A */%0Apublic class CountPrimes %7B%0A%0A    public int countPrimes(int n) %7B%0A        if (n %3C= 2) return 0;%0A%0A        int res = n %3E%3E 1; // remove even numbers%0A        int m = (int) Math.sqrt(n - 1); // p %3C= sqrt(n)%0A        boolean%5B%5D notPrime = new boolean%5Bn%5D;%0A%0A        for (int i = 3; i %3C= m; i += 2) %7B // traverse odd numbers only%0A            if (!notPrime%5Bi%5D) %7B%0A                for (int j = i * i, step = i %3C%3C 1; j %3C n; j += step) %7B // p%5E2, p%5E2 + p, p%5E2 + 2p ...%0A                    if (!notPrime%5Bj%5D) %7B%0A                        notPrime%5Bj%5D = true;%0A                        res--;%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A%0A        return res;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        CountPrimes cp = new CountPrimes();%0A        for (int i = 0; i %3C 1001; i++)%0A            System.out.println(i + %22 : %22+ cp.countPrimes(i));%0A    %7D%0A%0A%7D%0A

add 204 Count Primes