Sergei Khashin

Sieve of Eratosthenes

It took me a fast routime for small prime numbers (up to several billions). Natural aglorithm - sieve of Eratosthenes. There are its good realizations, but as part of a large and complex projects. Including them in my own program is not easy. Much easier to write my own version.

Only odd numbers are stored in a sieve, one bit for each. Therefore, N bytes is sufficient for prime numbers up to 16*N+1. To store all primes up to 1 million requires 63K bytes. 1G bytes enough for primes till 16 billions.

The package consists of two files:
Eratosthenes.h - header,
Eratosthenes.cpp - realization.

The header: 

typedef __int64	INT64;   // For Visual C++, change this definition for other compilers

void  Sieve_fill(INT64 maxN);   // fill sieve for primes till maxN
void  Sieve_free();             // free memory
INT64 Sieve_Size();             // return size in BYTES!
INT64 Sieve_maxN();             // return maximal N
bool  Sieve_isPrime( INT64 n);  // is prime(n)?
int   Sieve_save(char *fname);  // returns error code
int   Sieve_load(char *fname);  // returns error code
All prime numbers up to 4 billion are received for 72 sec. (AMD Athlon II X2 240, 2.8 GHz). The same with the replacement of __int64 to unsigned is done for 52 seconds., The difference is small, not worth trying. On the Intel Atom 1.66 GHz processor the same calculation takes 163 seconds (instead of 72).

Time to fill a sieve on the AMD Athlon II X2 240, 2.8 GHz
N max 106 107 224 108 228 229 109 231 232 233 234
time, sec 0.056 0.064 0.11 1.3 3.9 8.3 16.2 37 72 155 326

Here the main, working function of primality test: 

bool  Sieve_isPrime( INT64 n)	// is prime(n)?
{
	INT64 y = (n>>1)-1;
	unsigned x8 = (unsigned)(y>>3);
	if( x8>=size ) return true;
	unsigned x3 = (unsigned)(y &7);
	return  (v[x8]&(1< 0? 1 : 0;
}

Usage: 

#include "Eratosthenes.h"
...
    Sieve_fill(1000000);        // create list of primes till one mill.
    ...
    if( Sieve_isPrime(700001) ) {...} // check primularity
    ...
    Sieve_free();
Configure the package to different processors and compilers is reduced to an adjustment line in the header file: 
typedef __int64	INT64;   // For Visual C++, change this definition for other compilers
It should indicate the name of the type 64-bit integers.

If the requested size is too large, a table isn't created, more accurately, created a table of zero size.

If requested on primality test the number exceeds the sizes of the table, it is considered as composite, the error doesn't occur. So check in advance the maximum number for verification: 

INT64 Sieve_maxN();


free counters