AyrA

Prime finder

Jul 10th, 2017
666
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.58 KB | None | 0 0
  1. //See https://www.reddit.com/r/ProgrammerHumor/comments/6mhrb4/generating_primes_under_1000000000/dk1xqui/
  2. //Uncomment this, if you want single threading only
  3. //#define SINGLETHREAD
  4. using System;
  5. using System.Collections.Generic;
  6. using System.Linq;
  7. using System.Text;
  8. using System.Threading;
  9.  
  10. namespace PrimeFinder
  11. {
  12.     class Program
  13.     {
  14.         /// <summary>
  15.         /// Largest number to check
  16.         /// </summary>
  17.         const int MAXPRIME = 1000000;
  18.  
  19.         /// <summary>
  20.         /// Prime number checker main entry point
  21.         /// </summary>
  22.         static void Main()
  23.         {
  24.             //measure time
  25.             var Start = DateTime.UtcNow;
  26. #if SINGLETHREAD
  27.             int i = 3;
  28.             while (i <= MAXPRIME)
  29.             {
  30.                 if (isPrime(i))
  31.                 {
  32.                     //Whatever you do here will slow down the process
  33.                 }
  34.                 //Scan only odd numbers
  35.                 i += 2;
  36.             }
  37. #else
  38.             //Dynamically spawn as many threads as there are CPU cores
  39.             var Threads = new Thread[Environment.ProcessorCount];
  40.             var j = 3;
  41.             for (var i = 0; i < Threads.Length; i++)
  42.             {
  43.                 Threads[i] = new Thread(PrimeFinder)
  44.                 {
  45.                     //Kill threads if they still run on unexpected exit (CTRL+C handler for example)
  46.                     IsBackground = true,
  47.                     Name = "Prime finder",
  48.                     //This might slow things down but we test only
  49.                     Priority = ThreadPriority.BelowNormal
  50.                 };
  51.                 //Give each thread an individual start value
  52.                 Threads[i].Start(j);
  53.                 j += 2;
  54.             }
  55.             //Wait for completion
  56.             foreach (Thread T in Threads)
  57.             {
  58.                 T.Join();
  59.             }
  60. #endif
  61.             //Log the time it took.
  62.             Console.WriteLine("#END. Runtime: {0}", DateTime.UtcNow.Subtract(Start));
  63.             Console.ReadKey(true);
  64.         }
  65.  
  66.         /// <summary>
  67.         /// Thread loop for prime factor test
  68.         /// </summary>
  69.         /// <param name="o">Number of parallel threads</param>
  70.         private static void PrimeFinder(object o)
  71.         {
  72.             //Increase by double the processor count because we skip every second number (test odd numbers only)
  73.             int ProcCount = 2 * Environment.ProcessorCount;
  74.             int start = (int)o;
  75.             while (start <= MAXPRIME)
  76.             {
  77.                 if (isPrime(start))
  78.                 {
  79.                     //Whatever you do here will slow down the process,
  80.                     //especially if you print to console
  81.                 }
  82.                 start += ProcCount;
  83.             }
  84.         }
  85.  
  86.         /// <summary>
  87.         /// Checks if a given number is prime by simple modulo operation
  88.         /// </summary>
  89.         /// <param name="x">Number to check</param>
  90.         /// <returns>True if prime, false otherwise</returns>
  91.         private static bool isPrime(int x)
  92.         {
  93.             //This is probably not needed.
  94.             //I am not sure if the compiler would optimize it or calculate half of x during each loop iteration
  95.             var half = x / 2;
  96.             for (var i = 3; i <= half; i += 2)
  97.             {
  98.                 //Check if prime
  99.                 if (x % i == 0)
  100.                 {
  101.                     //Not prime, modulo was 0
  102.                     return false;
  103.                 }
  104.             }
  105.             //Prime
  106.             return true;
  107.         }
  108.     }
  109. }
Add Comment
Please, Sign In to add comment