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
