-----------------------------------

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