Post
Ask Question

Programming Que: Efficiently Check If Number is Prime

How to check if the number is prime or not? It’s very simple right? It is simple, however we can optimize it further.

Let’s first start with the most basic one (or by the book definition J). Here we will traverse from 2 to less than a given number and check if the number is divisible by any of them, if yes then it’s not prime.

  1. public static bool CheckPrimeNumber1(int num)  
  2. {  
  3.     if (num == 1)  
  4.         return false;  
  5.     for (int i = 2; i<num; i++)  
  6.     {  
  7.         if ((num % i) == 0)  
  8.         {  
  9.             return false;  
  10.         }  
  11.     }  
  12.     return true;  
  13. }  

Now let’s see a better one, it’s almost similar to the above, however the traversing is being done only till half.

  1. public static bool CheckPrimeNumber2(int num)  
  2. {  
  3.     if (num == 1)  
  4.         return false;  
  5.     for (int i = 2; i <= num/2; i++)  
  6.     {  
  7.         if ((num % i) == 0)  
  8.         {  
  9.             return false;  
  10.         }  
  11.     }  
  12.     return true;  
  13. }  

Now we will increase the efficiency, let’s park the numbers from a loop which are even and more than 2 (as they are obviously not prime, rightJ) and also start a loop from 3 and jumps by two numbers (as the even numbers have already been filtered).

  1. public static bool CheckPrimeNumber3(int num)  
  2. {  
  3.     if (num == 1)  
  4.         return false;  
  5.     if (num > 2 && (num % 2) == 0)  
  6.     {  
  7.         return false;  
  8.     }  
  9.     for (int i = 3; i <= num / 2; i+=2)  
  10.     {  
  11.         if ((num % i) == 0)  
  12.         {  
  13.             return false;  
  14.         }  
  15.     }  
  16.     return true;  
  17. }  
  18. return true;  

Now what? You are right J the most efficient one... In addition to the above, it’s only checking with the squares. It’s really bringing down the iterations to the lowest, right! Check it out.

  1. public static bool CheckPrimeNumber4(int num)  
  2. {  
  3.     if (num == 1)  
  4.         return false;  
  5.     if (num > 2 && (num % 2) == 0)  
  6.     {  
  7.          return false;  
  8.     }  
  9.     for (int i = 3; i*i <= num; i+=2)  
  10.     {  
  11.          if ((num % i) == 0)  
  12.          {  
  13.              return false;  
  14.           }  
  15.      }  
  16.      return true;  
  17. }  

One more thing please, do let me know about your comments/suggestion or if you have any better way to do this.