The implementation of a check if a number is a prime number or not is quite simple:

The logic is to find a positive integer less than or equal to the square root of input integer. If there is a divisor of number that is less than the square root of number, then there will be a divisor of number that is greater than square root of number. Hence, we have to traverse till the square root of number.

The time complexity of this function is O(√N) because we traverse from 1 to √N.

• input: 20, output: FALSE = no Prime Number
• input: 17, output: TRUE = Prime Number
`  internal static bool IsPrimeNr(int number)    {        if (number == 1) return false;        if (number == 2) return true;        if (number % 2 == 0) return false;          var squareRoot = (int)Math.Floor(Math.Sqrt(number));          for (int i = 3; i <= squareRoot; i += 2)        {           if (number % i == 0) return false;        }          return true;   }`

We can enhance a common simple for() loop with a Parallel.For() loop in order to increase performance. Well, no, not really a Parallel.For() loop since we can not implement a step size different than "1" with the Parallel.For()

`for (int i = 3; i <= squareRoot; i += 2) `

since the implementation of Parallel.For() has no overload for a different step size.

We rather have to generate an integer sequence and iterate over that sequence with Parallel.ForEach() [where we can't just simply return false within the loop but rather have to breakout from the loop] as shown in the code below:

`using System;using System.Collections.Generic;using System.Threading;using System.Threading.Tasks;					public class Program{   public static void Main()   {      Console.WriteLine(IsPrimeNr(42));      Console.WriteLine(IsPrimeNr(311));      Console.WriteLine(IsPrimeNr(5071));      Console.WriteLine();      Console.WriteLine(IsPrimeNrParallel(42));      Console.WriteLine(IsPrimeNrParallel(311));      Console.WriteLine(IsPrimeNrParallel(5071));		      Console.ReadLine();     }		  // standard for loop  internal static bool IsPrimeNr(int number)    {        if (number == 1) return false;        if (number == 2) return true;        if (number % 2 == 0) return false;          var squareRoot = (int)Math.Floor(Math.Sqrt(number));          for (int i = 3; i <= squareRoot; i += 2)        {           if (number % i == 0) return false;        }          return true;   }	   // parallel for loop   internal static bool IsPrimeNrParallel(int number)     {        if (number == 1) return false;        if (number == 2) return true;        if (number % 2 == 0) return false;          var squareRoot = (int)Math.Floor(Math.Sqrt(number));        var res = true;			      Parallel.ForEach(SteppedIterator(3, squareRoot, 2), (i, state) =>       {         if (number % i == 0)          {            res = false;            state.Break();         }		       });			        return res;     }	   // int sequence for simmulationg "for step size = 2" for the parallel loop   internal static IEnumerable<int> SteppedIterator(int startIndex, int endIndex, int stepSize)   {      for (int i = startIndex; i < endIndex; i = i + stepSize)      {         yield return i;      }   }   }`