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