//See https://www.reddit.com/r/ProgrammerHumor/comments/6mhrb4/generating_primes_under_1000000000/dk1xqui/
//Uncomment this, if you want single threading only
//#define SINGLETHREAD
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace PrimeFinder
{
    class Program
    {
        /// <summary>
        /// Largest number to check
        /// </summary>
        const int MAXPRIME = 1000000;

        /// <summary>
        /// Prime number checker main entry point
        /// </summary>
        static void Main()
        {
            //measure time
            var Start = DateTime.UtcNow;
#if SINGLETHREAD
            int i = 3;
            while (i <= MAXPRIME)
            {
                if (isPrime(i))
                {
                    //Whatever you do here will slow down the process
                }
                //Scan only odd numbers
                i += 2;
            }
#else
            //Dynamically spawn as many threads as there are CPU cores
            var Threads = new Thread[Environment.ProcessorCount];
            var j = 3;
            for (var i = 0; i < Threads.Length; i++)
            {
                Threads[i] = new Thread(PrimeFinder)
                {
                    //Kill threads if they still run on unexpected exit (CTRL+C handler for example)
                    IsBackground = true,
                    Name = "Prime finder",
                    //This might slow things down but we test only
                    Priority = ThreadPriority.BelowNormal
                };
                //Give each thread an individual start value
                Threads[i].Start(j);
                j += 2;
            }
            //Wait for completion
            foreach (Thread T in Threads)
            {
                T.Join();
            }
#endif
            //Log the time it took.
            Console.WriteLine("#END. Runtime: {0}", DateTime.UtcNow.Subtract(Start));
            Console.ReadKey(true);
        }

        /// <summary>
        /// Thread loop for prime factor test
        /// </summary>
        /// <param name="o">Number of parallel threads</param>
        private static void PrimeFinder(object o)
        {
            //Increase by double the processor count because we skip every second number (test odd numbers only)
            int ProcCount = 2 * Environment.ProcessorCount;
            int start = (int)o;
            while (start <= MAXPRIME)
            {
                if (isPrime(start))
                {
                    //Whatever you do here will slow down the process,
                    //especially if you print to console
                }
                start += ProcCount;
            }
        }

        /// <summary>
        /// Checks if a given number is prime by simple modulo operation
        /// </summary>
        /// <param name="x">Number to check</param>
        /// <returns>True if prime, false otherwise</returns>
        private static bool isPrime(int x)
        {
            //This is probably not needed.
            //I am not sure if the compiler would optimize it or calculate half of x during each loop iteration
            var half = x / 2;
            for (var i = 3; i <= half; i += 2)
            {
                //Check if prime
                if (x % i == 0)
                {
                    //Not prime, modulo was 0
                    return false;
                }
            }
            //Prime
            return true;
        }
    }
}