An exceedingly common question asked in coding interviews is to write a function, method, algorithm, whatever to determine if a number is prime. Prime numbers have a wide range of applications in computer science, particularly with regard to cryptography. The idea is that factoring large numbers into their prime factors is extremely difficult.
“Because both the system’s privacy and the security of digital money depend on encryption, a breakthrough in mathematics or computer science that defeats the cryptographic system could be a disaster. The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers.” -Bill Gates, The Road Ahead
Granted, for most programming positions, this question is asked not to test the candidate’s knowledge of determining primality, but rather as an exercise to gain insight into his or her thought process on a well-understood problem.
The Naive Approach
The common approach to this problem is a simple brute-force solution. That is, divide the number 
This is also incredibly inefficient. We can improve it a bit by checking factors from 
These are the solutions your interviewer will probably be looking for, starting with the most naive approach and improving from that, but even the revised version is not very efficient.
Probabilistic Testing
A slightly more sophisticated way to go about checking primality is to use probabilistic testing. Probabilistic tests use numbers, a, chosen at random from some sample space. This technique introduces a probability of error which can be reduced by repeating the test with independently selected a values.
There are a number of different probabilistic primality tests, some better than others. One of the more simple probabilistic primality tests is the Fermat primality test, which is based on Fermat’s little theorem and is used in PGP and RSA encryption. The theorem states that, if p is prime, then 
This method will indicate if p is a probable prime, but since we’re only selecting a single a value, the possibility of p being incorrectly identified as a prime is high. In such situations, a is referred to as a Fermat liar. As suggested earlier, we can minimize this probability by repeating the process k times and selecting k witnesses.
This allows us to improve the probability of correctly determining the primality of p by performing k iterations, in which the probability of error becomes vanishingly small for large values of k. Nonetheless, being probabilistic in nature, this algorithm is inherently nondeterministic, which is really just a fancy way of saying we can get different results on different runs for the same input.
Polynomial, Deterministic Algorithms
Only within the last decade has a deterministic, polynomial-time algorithm for testing primality been developed. In 2002, the AKS primality test was discovered, moving primality into the P complexity class. The algorithm determines if a given number is prime or composite in polynomial time, and it’s the first to be simultaneously general, polynomial, unconditional, and deterministic. Try busting that out at an interview.
For the mathematically inclined (of which I do not consider myself), primality presents some interesting uses and even more interesting problems. It’s remarkable that a fast, deterministic solution for such a well-defined problem was found only in the last 10 years, and it makes you wonder what tough problems will be solved in the next 10 years and beyond.
Follow @tyler_treat
In terms of on-the-hoof interview answers, variations on the Newton-Raphson method (convergent scaled binary-chop – square of double versus square of half) are occasionally given. As integer squaring is often very much faster than extracting a root, it’s quite cute… although not as quick as AKS on truly huge numbers.