Finding primes

The sieve of Eratosthenes shown in the picture is an appropriate procedure if one wants to find every prime, but testing whether an individual number is prime can be done much more efficiently, as in PrimeQ[n] in Mathematica, for example by using Fermat's so-called little theorem that Mod[a^{p - 1}, p]  1 whenever p is prime. The n^th prime Prime[n] can also be computed fairly efficiently using ideas from analytic number theory (see the next note).