Interview Coding Question - Prime Number

What's Prime Number

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Simplest algorithm but most expensive

bool isPrime(int n)

{

      if (n<=1) return false;

for (int i=2; i < n; ++i)

if (n%i==0)

return false;

return true;

}
If you stop here, you barely can be hired as programmer.

A little bit optimized 

/// If the number can NOT be exactly divided by 2, no need to test 4, 6, 8...

bool IsPrime (int n)

{

if (n <= 1) return false;

if (n % 2 == 0)

return false;

else 

for (int i=3; i < n; i+=2)

if (n%i==0)

      return false;

return true;

}

Further optimization with a theory  

if  is composite (with a and b ≠ 1) then one of the factors a or b is necessarily at most .

bool IsPrime (int n)

{

if (n <= 1) return false;

float sqrt_num = sqrt(n)

for (int i=2; i < sqrt_num; ++i)

if (n%i==0)

return false;

return true;

}

Note
Prime generation algorithm is heavily tested during interview, because it can test the interviewee's basic math knowledge, logical thinking and the sense to chase excellence which are a great programmer requires.
Prime algorithm optimization is a very very deep topic. You are NOT expected to be able to finish it with the highest efficiency algorithm if the position you apply is a junior / medium level software developer. Otherwise the interview will last more than 2 hours, and very likely the interviewer will think you have guessed the question and are prepared.

Reference
http://en.wikipedia.org/wiki/Prime_number

http://program-think.blogspot.com/2011/12/prime-algorithm-1.html