Checking for a prime number


Ok, looking back at the original post I’m nearly regretting it as I need to find the time to actually write these – but at least this one was quick and simple. In fact it may be too simple to use as a tech test, but anyways here it is.

A prime number is any number greater than 1 which is only divisible by itself and 1. The method I use here simply checks all the values up to the number under investigation to see if division by them would leave a remainder of zero. There are probably faster ways to do this using smarter maths, and if you know of one, please post a comment!

 

 private static bool IsPrime(int num)
{
if (num <= 1)
{
return false;
}

for (int i = 2; i < num; i++)
{
if (num % i == 0)
{
return false;
}
}

return true;
}
Comments (3)

  1. Comet says:

    You can go twice as fast, if you have a separate test for divisibility by 2, and iterate over the odd numbers as test divisors.

    You can finish your testing by an exponent of .5; namely, once your test divisor exceeds the square root of your candidate prime, you can terminate your loop.

  2. Comet says:

    If you are looking for clever maths, then see the "Agrawal–Kayal–Saxena primality test" as a  general, polynomial, deterministic, and unconditional algorithm.  If a candidate can explain it to you, then they are a "prime" candidate.  😉

  3. Javier Andres Caceres Alvis says:

    Hello Dermot,

    I'd like to propose another implementation:

           private static bool IsPrime(uint n)

           {

               if (n == 0 || n == 1)

               {

                   return false;

               }

               if (n == 2 || n == 3)

               {

                   return true;

               }

               double squareRoot = Math.Sqrt(n);

               for (uint i = 2; i <= squareRoot; i++)

               {

                   if (n % i > 0)

                   {

                       return false;

                   }

               }

               return true;

           }

    The first part just check common cases. The second part, if the prime really exists then it should be num=p*q, then we should really check until the root square. Also I used uint (just positive integers).

    Cheers,

    Javier Andres Caceres Alvis

    jacace.wordpress.com