-----------------------------------
Brightguy
Tue Nov 02, 2010 10:32 pm
Optimized Sieve of Eratosthenes
-----------------------------------
This is an optimized implementation of Eratosthenes' sieve. It runs in O(n log n / log log n) bit operations, as opposed to the standard O(n log n log log n). This is the best known complexity AFAIK, however it still requires O(n) space, which is not the best known. This makes it not practical for very large n (of course exactly when you'd want to use it; I just wanted to make sure that I understood the algorithm).
It computes the first 10 billion primes in 46 seconds on my work machine. (On a 32-bit machine n will probably be limited by 2^31-1.)
#include
#include
#include
#include
#include
#ifdef __LP64__
#define LONGSIZE 8
#define SHIFT 6
#define MASK 63
#else
#define LONGSIZE 4
#define SHIFT 5
#define MASK 31
#endif
#define PRINTPRIMES // Print a list of the primes
#define PRINTCOUNT // Print a count of the primes
#define PRINTTIME // Print the computation time
static int smallprimes
EDIT: Note there are almost no multiplications in the program; this is to help meet the stated bit complexity. However, previously I sillily had "if(ps+1