** Next:** 4.2 Trial division
** Up:** 4 Primes and Composites
** Previous:** 4 Primes and Composites

The most traditional way of finding prime numbers is the sieve of
Eratosthenes. Suppose we are given a list *l* of all primes less than
the integer *n*. Then *n* is prime if it is not a multiple of any of
these. Thus, if we have also a list *m*, so that *m*_{i} is the least
multiple of the prime *l*_{i} that is not less than *n*, we can compare
*n* with elements of this list to decide if it is a prime. The
incremental step can then be carried out as follows. We run through
the list *m*_{i} look for *n*. Whenever we find *n* we note that *n* is
composite and replace *m*_{i} by *m*_{i} + *l*_{i}. If we come to the end of the
list without find such an *i*, then *n* is a prime so we append it to
the end of *l*; we also append 2**n* to the end of *m*. In this way we
can iteratively generate the list of all primes!
Clearly as the list grows larger this is taking up more and more space
and time. Moreover, it gives us no way of checking if a given number
is prime except by running through all primes before it.

** Next:** 4.2 Trial division
** Up:** 4 Primes and Composites
** Previous:** 4 Primes and Composites
Kapil Hari Paranjape
2002-10-20