A prime number is a number greater than 1 whose only divisors are itself and 1. This definition suggests that, to determine whether n is prime, we should painstakingly divide n by 2, then by 3, and so on, until one of the divisors divides evenly or we have tested n − 1. Hardly quick, and even harder to do mentally… Fortunately, a little arithmetic greatly reduces the number of operations required, making it possible to determine mentally whether n is prime for many numbers that are not too large.
The sieve pays off ------------------
Eratosthenes, director of the Library of Alexandria and a correspondent of Archimedes, is credited with devising a method for finding all the prime numbers below a previously chosen value N: write down the integers from 2 to N, keep 2 and cross out all its multiples, then keep 3 and cross out all its multiples, then keep 5 (since 4 has been crossed out) and cross out all its multiples, and so on. At the end, only the prime numbers between 2 and N remain uncrossed.
To gauge the efficiency of the sieve of Eratosthenes, note that if the product of two numbers p and q equals n, then at least one of p and q is less than or equal to n\sqrt{n}. If both exceeded n\sqrt{n}, their product pq would exceed n×n=n,\sqrt{n} \times \sqrt{n} = n, even though pq = n. It follows that, in the sieve of Eratosthenes, once the multiples of each integer n have been crossed out for every n≤Nn \le \sqrt{N}, there is nothing left to cross out: the job is done.
This full sieving procedure is of course not really suitable for mental arithmetic, but we can draw inspiration from it to determine whether a given integer a is prime. If a is not prime, it can be written as pq and, by the preceding observation, one of these two factors is at most a.\sqrt{a}. We therefore need only test whether a is divisible by 2, 3, and so on up to a,\sqrt{a}, which is still faster than going all the way to a − 1.