Sdílet prostřednictvím

Checking for a prime number

  • Článek

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

  • Anonymous
    April 11, 2013
    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.

  • Anonymous
    April 11, 2013
    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.  ;-)

  • Anonymous
    November 18, 2013
    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