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;
      }
   }
   
}