Skip to the content of the web site.

Lesson 149u: Sieve of Eratosthenes

Previous lesson Next lesson

Suppose you wanted to find all prime numbers less than or equal to a given number $N$. The easiest way to do this is to create an array that can hold the integers from $1$ to $N$. We will initialize the array so that array[k] == k. If we ever determine that a number k is not prime, we will assign array[k] = 0;. By definition, $1$ is not prime, so we will immiedately assign array[1] = 0;. Next starting with $2$, if we determine that k is prime (meaning that array[k] == k, we have then determined that all integer multiples of k up until the end of the array to be composite, so we set:

array[2*k] = 0;
array[3*k] = 0;
array[4*k] = 0;
array[5*k] = 0;


until we reach the end of the array.

We then search forward in the array until we find the next k such that array[k] == k and repeat the above process.

This is called the Sieve of Eratosthenes. Implement a function that prints all prime numbers up to but not exceeding $N$ in the format:

2, 3, 5, 7, 9, 11, 13, ...

Be sure not to have a comma after the last prime number. Your function declaration should be:

void print_primes( unsigned long N );

As an aside, why is $1$ not prime? In general, many of the most interesting properties of prime numbers are not true if $1$ is considered to be prime. For example, that every number has a unique prime factorization is false if $1$ is a prime, for $6 = 2 \times 3 = 2 \times 3 \times 1 = 2 \times 3 \times 1 \times 1 \times \cdots$. Thus, if $1$ were said to be prime, then almost every interesting theorem about prime numbers would have to be worded as all prime numbers except for $1$.

In the previous function, you could have easily printed the prime number every time you found one. You would start by automatically printing "2", and then for every subseuent prime number n you find, print ", n". However, suppose you wanted to do the following:

If you have found $n$ primes less than or equal to $N$, return an array of size $n$ containing those $n$ prime numbers.

Now, beause you don't know how large an array to build, you will have to temporarily store prime numbers, and the easiest way is to look at the array array; however, looking through the entire array of capacity $N$ to find $n$ primes is unnecessarily expensive, especially when you know mathematically that the number of primes less than or equal to $N$ will be approximately $n \approx \frac{N}{\ln(N)}$. This estimates there are approximately $72382$ prime numbers less than or equal to one million. There are in fact $78498$ primes less than or equal to one million, so this approximation is not unreasonable; however, it is not exact.

It can be shown that the relative error drops at approximately $0.24 n^{-0.085}$, so the relative error actually goes to zero as $n$ becomes large.

Devise a scheme whereby you use the existing array to store all the prime numbers without having to walk through the entire array to retrieve all of them.

Array<unsigned long> *primes( unsigned long N );

Previous lesson Next lesson