public class PrimeSieve {
    public static final int SIZE  = 50000000;
    public static final int SIZE2 = 5000000;

    public static boolean isprime(int n) {
        if (n < 2) {
            return false;
        }
        else if (n == 2) {
            return true;
        }
        else if (n % 2 == 0) {
            return false;
        }
        else {
            for (int i=3; i*i<=n; i+=2) {
                if (n%i==0) {
                    return false;
                }
            }
            return true;
        }
    }
    
    public static void primesieve(boolean[] arr) {
        int len = arr.length;

        java.util.Arrays.fill(arr, true);

        if (len > 0) arr[0] = false;
        if (len > 1) arr[1] = false;

        for (int i=4; i<len; i+=2) {
            arr[i] = false;
        }

        for (int i=3; i*i<=len; i+=2) {
            if (arr[i]) {
                for (int j=i<<1; j<len; j+=i) {
                    arr[j] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        boolean[] arr;
        long t1,t2;

        // warm up and test
        arr = new boolean[10000];
        primesieve(arr);
        for (int i=0; i<10000; i++) {
            if (isprime(i) != arr[i]) {
                throw new RuntimeException("Error in primesieve/isprime at " + i);
            }
        }

        // benchmark primesieve
        arr = new boolean[SIZE];
        t1 = System.currentTimeMillis();
        primesieve(arr);
        t2 = System.currentTimeMillis();

        System.out.println((double)(t2-t1)/1000.0);

        // benchmark isprime
        t1 = System.currentTimeMillis();
        for (int i=0; i<SIZE2; i++) {
            boolean b = isprime(i);
        }
        t2 = System.currentTimeMillis();

        System.out.println((double)(t2-t1)/1000.0);
    }
}