using System;

public class PrimeSieve {
    public const int SIZE  = 50000000;
    public const int SIZE2 = 5000000;

    public static bool 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(bool[] arr) {
        int len = arr.Length;

        for (int i=0; i<arr.Length; i++) {
            arr[i] = 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=2*i; j<len; j+=i) {
                    arr[j] = false;
                }
            }
        }
    }

    public static void Main() {
        bool[] arr;
        long t1,t2;
        int SIZE  = 50000000;
        int SIZE2 = 5000000;

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

        // benchmark primesieve
        arr = new bool[SIZE];
        t1 = DateTime.Now.Ticks * 100;
        primesieve(arr);
        t2 = DateTime.Now.Ticks * 100;

        Console.WriteLine((double)(t2-t1)/1000000000.0);

        // benchmark isprime
        t1 = DateTime.Now.Ticks * 100;
        for (int i=0; i<SIZE2; i++) {
            bool b = isprime(i);
        }
        t2 = DateTime.Now.Ticks * 100;

        Console.WriteLine((double)(t2-t1)/1000000000.0);
    }
}