Compute the prime numbers using the Eratosthenes algorithm.

This program computes the prime numbers and print them. It is based on the Eratosthenes algorithm. Bascically, for a given number we must check that it can't be divided by the prime numbers below it. In fact we can stop when we checked up to sqrt(N).

The prime numbers are stored in a bitmap because they occupy less room in memory. There are 6542 primes below 65536. To keep them in a list, we need 13084 bytes (if we use unsigned short). In our case, the bitmap contains only 8192 bytes (65536 bits).

To compute the 6542 first primes:

 GCC 2.95.2 293159129 cycles (146.6 s)
 GCC 2.95.3 293100142 cycles (146.6 s) 
 GCC 3.0.4 277176107 cycles (138.6 s)
 

Source file: primes.c