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

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