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[ap - 1, p] 1 whenever p is prime. The nth prime Prime[n] can also be computed fairly efficiently using ideas from analytic number theory (see the next note).

Image Source Notebooks:

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