using System;
using System.Diagnostics;

namespace Prime
{
    class Program
    {
        private static int operations;
        private static double time;

        public static void Test()
        {
            long[] numbers =
            {
                100913,
                1009139,
                10091401,
                100914061,
                1009140611,
                10091406133,
                100914061337,
                1009140613399
            };

            Console.WriteLine(
                "{0, 20}{1, 20}{2, 20} {3, 20}",
                "N",
                "Prime?",
                "Operations",
                "Time");

            foreach (long n in numbers)
            {
                bool p = IsPrimeMarcin(n);
                Console.WriteLine(
                    "{0, 20}{1, 20}{2, 20}{3, 20}ms",
                    n,
                    p,
                    operations,
                    time.ToString("0.000"));
            }
        }

        static double GetElapsedTime(long start)
        {
            return (Stopwatch.GetTimestamp() - start) * (1000.0 / Stopwatch.Frequency);
        }

        // wersja naiwna
        static bool IsPrimeNaive(long n)
        {
            long start = Stopwatch.GetTimestamp();
            operations = 0;
            if (n < 2)
            {
                operations++;
                time = GetElapsedTime(start);
                return false;
            }
            else if (n < 4)
            {
                operations++;
                time = GetElapsedTime(start);
                return true;
            }
            else if (n % 2 == 0)
            {
                operations++;
                time = GetElapsedTime(start);
                return false;
            }
            else
            {
                for (long u = 3; u < n / 2; u += 2)
                {
                    operations++;
                    if (n % u == 0)
                    {
                        time = GetElapsedTime(start);
                        return false;
                    }
                }
            }

            time = GetElapsedTime(start);
            return true;
        }

        // wersja efektywna
        static bool IsPrime(long n)
        {
            long start;
            start = Stopwatch.GetTimestamp();
            operations = 0;
            if (n < 2)
            {
                operations++;
                time = GetElapsedTime(start);
                return false;
            }
            else if (n < 4)
            {
                operations++;
                time = GetElapsedTime(start);
                return true;
            }
            else if (n % 2 == 0)
            {
                operations++;
                time = GetElapsedTime(start);
                return false;
            }

            long[] values = { 0, 2, 6, 8, 12, 14, 18, 24, 26 };

            for (long u = 5; u * u <= n - 30; u += 30)
            {
                foreach (long value in values)
                {
                    operations++;
                    if (n % (u + value) == 0)
                    {
                        time = GetElapsedTime(start);
                        return false;
                    }
                }
            }

            time = GetElapsedTime(start);
            return true;
        }

        // wersja naiwna
        static bool IsPrimeMarcin(long n)
        {
            long start;
            start = Stopwatch.GetTimestamp();

            // Corner cases
            if (n <= 1)
            {
                operations++;
                time = GetElapsedTime(start);
                return false;
            }
            if (n <= 3)
            {
                operations++;
                time = GetElapsedTime(start);
                return true;
            }

            // This is checked so that we can skip
            // middle five numbers in below loop
            if (n % 2 == 0 || n % 3 == 0)
            {
                operations++;
                time = GetElapsedTime(start);
                return false;
            }

            for (long i = 5; i * i <= n; i += 6)
            {
                operations++;
                time = GetElapsedTime(start);
                if (n % i == 0 || n % (i + 2) == 0)
                    return false;
            }

            return true;
        }

        static void Main(string[] args)
        {
            Test();
            Console.ReadKey();
        }
    }
}