PrimeSieve is a C# library that generates primes using a Segmented Sieve of Eratosthenes implementation. The library allows you to calculate all primes up to given value. It calculates all the primes below int.MaxValue (~2.4 billion) in only 37.35 seconds using a single core, or 7.17 seconds using all cores (6 core Intel Core i7-7800X 3.5GHz). I initially wrote the code due to requiring the generation of primes to solve problems at Project Euler. Currently PrimeSieve can only count all primes to int.MaxValue, however increasing this value is noted on the roadmap below.
When searching for primes up to int.MaxValue, I found that a bool array of size [int.MaxValue] broke .NET’s 2GB object limit. To solve this, I came up with what I later found to be known as the Segmented Sieve. This approach divides the numbers to check for primality into ranges (segments), and then iterates over each of these returning its primes.
The library is produced as a DLL file, so simply add the DLL as a reference to your project and follow the code example below.
The DLL is directly available from inside the solution here
using System;
using System.Diagnostics;
using JoshuaaM.PrimeSieve;
namespace PrimeSieveExample
{
class Program
{
static void Main(string[] args)
{
Console.Title = "PrimeSieve";
Stopwatch sw = new Stopwatch();
int countOfPrimesToSearchForMax = int.MaxValue;
Console.WriteLine("Searching for primes below: {0}", countOfPrimesToSearchForMax);
Console.WriteLine("Starting to search for primes without multithreading");
sw.Start();
int[] primes = PrimeSieve.GeneratePrimesToMax(countOfPrimesToSearchForMax);
sw.Stop();
Console.WriteLine("Completed without multithreading");
Console.WriteLine("Time: {0}", sw.Elapsed);
Console.WriteLine("Primes found: {0}", primes.Length);
sw.Reset();
Console.WriteLine("Starting to search for primes with multithreading");
sw.Start();
primes = PrimeSieve.GeneratePrimesToMax(countOfPrimesToSearchForMax, true);
sw.Stop();
Console.WriteLine("Completed with multithreading");
Console.WriteLine("Time: {0}", sw.Elapsed);
Console.WriteLine("Primes found: {0}", primes.Length);
PrimeSieve.SavePrimesToFile(primes, "primes.dat");
//primes = PrimeSieve.LoadPrimesFromFile("primes.dat");
Console.ReadLine();
}
}
}
Add ability to read/write primes to a file
Add ability to read/write primes to a compressed file
Add CPU multithreading
Add ability for MaxNumber to be greater than int.MaxValue long (64 bit)