import java.util.BitSet;

public class IntSieve {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int root = 10000;
        int max = root * root;
        BitSet noPrime = new BitSet(max >> 1);

        int countPrimes = max >> 1;
        for (int i = 3; i < root; i += 2) {
            if (noPrime.get(i >> 1)) {
                continue;
            }
            for (int x = i * i; x < max; x += i) {
                if ((x & 1) != 0) {
                    noPrime.set(x >> 1);
                }
            }
        }

        countPrimes -= noPrime.cardinality();

        long end = System.currentTimeMillis();

        System.out.println("Primes < " + max + ": " + countPrimes);
        System.out.println("Time: " + (end - start) + " ms");
    }
}