import java.util.*;

public class exp {
    public static void main(String[] s) {

        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
        bench();
    }

    static final int n=2000000;
    static void bench() {

        long start = System.currentTimeMillis();
        int[]bits = new int[(n / 32) + 1];

        for(int i=2;i<=n;i++){
            set(bits, i);
        }

        int count = calc(bits);
        long end = System.currentTimeMillis();
        System.out.println("Ilosc: " + count);
        System.out.println((end - start) + " ms.");

    }

    private static int log2(int n){
        int log = 0;
        while ((n >>>= 1) != 0) log++;
        return log;
    }

    static int bit(int pos){
        return 1 << (pos % n);
    }

    static void set(int[]bits, int pos) {
        bits[pos >>> 5] |= bit(pos);
    }

    static void clear(int[]bits, int pos) {
        bits[pos >>> 5] &= ~bit(pos);
    }

    static boolean test(int[]bits, int pos) {
        return (bits[pos >>> 5] & bit(pos)) != 0;
    }

    static int calc(int[]b) {
        int i = 2;
        int count = 0;
        while (i*i<=n) {
            if(test(b, i)) {
                count++;
                calcInner(b, 2*i);
            }
            i++;
        }
        while (i<=n) {
            if(test(b, i)) {
                count++;
            }
            i++;
        }
        return count;
    }

    static void calcInner(int[]b, int k) {
        while(k<=n) {
            clear(b, k);
            k = k + 1;
        }
    }
}