How to sieve prime numbers?

The algorithm is so simple that it even becomes difficult to explain it. A prime number cannot be divided by any number except 1 and itself. It is obvious that no number (non-primes, too) can be divided by any number greater than itself.

Spoken mathematically, (for all numbers n):((for all numbers i>n): n mod i <> 0). And, the definition of a prime number is: (n is prime number) <=> ((for all numbers 1<i<n):n mod i <> 0).

Now imagine an array of all numbers from 2 to any upper limit, say, 10 million. Each number has a flag whether the number is checked or not. The array is initialized with all numbers unchecked.

You now begin with two and proceed upwards. Whenever you encounter an unchecked number, it is a prime number. The trick is, you now check out all multiples of this number, that is, all numbers that are dividable by this number and which are therefore not prime.

Now whenever you get to a number n, you have checked out all multiples of 1<i<n, and if n is not checked, it is therefore prime. You'll understand the algorithm best if you take a piece of paper and do it by hand maybe for 1..100.

Of course, there are two problems:

  1. You need an array for the flags of all numbers in the interval from which you want to extract the primes. If you want to calculate all primes from 1 to 1.000.000, you need an array with 1.000.000 elements.
  2. You must begin the algorithm with 2. The interval must not necessarily start with 1, but nevertheless you must begin the ruling-out with all potential dividents.

The below program does implement this sieve, plus a few goodies and optimizations.

I have to admit, because of not handling some special cases, it will identify 2 as not prime and 1 as prime. While it is clearly wrong about 2, we could discuss about 1 being prime or not ...

Compiling and Running

You can get the source code sieve.c here(1kB). It shouldn't make any problems compiling. You can also download an executable sieve.exe for Windows.

The program takes an upper limit as parameter, i.e. it will compute prime numbers up to this number given on the command line. This upper limit defaults, for historic reasons, to 14.000.000.

This should take substantially less than one minute on a workstation and on fast PCs (our HP/UX's here need 23 seconds). It will then prompt you for the beginning and end of an interval (you may enter even numbers), display all prime numbers in this area and then prompt again. The program terminates when you enter an end of interval that is less or equal the beginning of the interval.

Frank Pilhofer <fp -AT-> Back to the Homepage
Last modified: Thu Mar 21 08:50:18 1996