Prime Number Sieve: Primes to 1 Billion in 2 Minutes

August 06, 2010
Generating a list of all prime numbers up to a specified limit is easy using the famous algorithm known as the Sieve of Eratosthenes. To identify all primes up to a number N using this algorithm only requires explicitly identifying all primes up to Sqrt(N) since a composite number will have a minimum factor that is prime and this must be less than or equal to Sqrt(N).

Primesieve is a C# console application for .NET Framework 3.5+ which implements the Sieve of Eratosthenes. It can be used to identify and accumulate primes in memory up a specified number N limited by the computer RAM and of course execution time. (Storing the primes in memory for further analysis and manipulation can be handy for different applications.) It is possible to generate a list of primes up to one billion with a modest amount of RAM (~ 500 Mb). Primesieve uses a C# BitArray type to efficiently store the prime/composite status of all numbers up to N. For N = 10^9 the BitArray uses ~ 119 Mbyte of memory. Since the maximum number of elements for the x64 platform for a BitArray is Int32.MaxValue = 2,147,483,647, this is the maxumum number of primes that can be indexed with a single BitArray. After performing the sieve, the identified primes up to N are copied to an int array (4 bytes per element, maximum value of int 2,147,483,647). For N=10^9, there are 50,847,534 primes which translates into an int array of size ~ 194 Mbytes. Considering RAM, this translates into a total modest memory requirement for execution of about 300 Mbytes. Although it is easy to extend the range N available for searching by using the long type (8 bytes) with a range up to 9,223,372,036,854,775,807, the index range for the arrays is still limited to Int32.MaxValue. Further the computation time and RAM storage requirements increase so quickly that using this algorithm for directly identifying primes is not practical much above N ~ 10^9. For example, for N = 10^10 at least ~ 3.5 Gbytes of RAM would be required for execution if all 455,052,511 primes up to 10^10 could be stored as an array of type long, say with an x64 system.

The utility will optionally write a file with all primes as either a text file with each prime number on a separate line, a text file conveniently formatted in array initializer form (which can be copy/pasted into source code) or a more compact binary int32 file, with 4 bytes for each prime in little-endian order.

For a 2.8 GHz PIV computer with 2Gb (much more than needed), execution time for N = 10^9 is about 2 minutes.

Requirements: WinXP sp3 or higher; Microsoft .NET Framework 3.5 or higher

Download primesieve.exe v. 1.0.0.1 (11,392 bytes digitally signed)

References