Chapter 4: Systems Based on Numbers

Section 4: The Sequence of Primes

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 below).

From Stephen Wolfram: A New Kind of Science [citation]