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

## 4.1 Eratosthenes' sieve

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 mi is the least multiple of the prime li 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 mi look for n. Whenever we find n we note that n is composite and replace mi by mi + li. 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