11,433,997 members (64,419 online)

# Find Prime Numbers in C# Using the Sieve of Eratosthenes

, 3 Oct 2011 CPOL
 Rate this:
This tip illustrates a simple C# console program that uses the Sieve of Eratosthenes algorithm to quickly find prime numbers.
Ever been tasked to come up with lists of prime numbers and you want to use the Sieve of Eratosthenes[^] to do so, but aren't quite sure how to code it up in C#? If so, then this simple console program written with .NET should do the trick:

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace PrimeFinder
{
class Program
{
static void Main(string[] args)
{
// this method encodes the Sieve of Eratosthenes
// with some intelligent shortcuts, such as excluding
// all even numbers greater than 2 etc.
try
{
List<string> outputLines = new List<string>();

// read in the numbers specified in the argument
string[] numbersList = File.ReadAllLines(args[0]);
foreach(string number in numbersList) {
int N = Int32.Parse(number);
List<int> primeCandidates = new List<int>(N);
if (N==2)
{
outputLines.Add("2\r\n");  // trivial case
continue;
}
if (N==1)
{
throw new InvalidArgumentException("The number one is trivially prime.");
}

// initialize primeCandidates with 2
// and the list of all odd numbers
// less than N -- because all even numbers
// save 2 are nonprime by definition
primeCandidates.Add(2); // the number 2 is always prime
for (int i = 2; i <= (N+1)/2; i++)

for(int j = 0;j < primeCandidates.Count;++j) {
// initialize first prime
int prime = primeCandidates[j];

// use for loop to go through the multiples of the prime
for( int multiple = 2;multiple*prime <= N;++multiple) {
if (prime == 2) break; // duh, 2 is a prime

// skip all even multiples of 2
if ((multiple * prime) % 2 == 0)
continue;

// don't bother removing an item that
// is not even in the list
if (!primeCandidates.Contains(multiple * prime))
continue;

primeCandidates.Remove(multiple * prime);
}
}

// put together a string representing
// current output line of primes
string currentOutputLine = string.Empty;
foreach (int value in primeCandidates)
currentOutputLine += value.ToString() + ',';
currentOutputLine =
currentOutputLine.Remove(currentOutputLine.Length - 1);
currentOutputLine += "\r\n"; // Windows CRLF encoding

Console.Write(currentOutputLine);

// write a line to the output file for
// each list of prime
// candidates generated
}

File.WriteAllLines(args[1], outputLines);

Console.WriteLine("DONE computing primes");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
}
}
}```

## About the Author

Software Developer (Senior) Corrugated Technologies, Inc.
United States
From Fridley, Minnesota and I like computer programming! When I got started, I was working mostly with Windows GUI programming in C/C++. Then later on I worked with COM/DCOM for a school internship. I used COM/DCOM to write an ad hoc cluster server and job-running environment for a cluster of 24 Windows-based high-end visualization workstations. I moved on to C# and have been working in C# and Windows Forms ever since. I have yet to embrace Silverlight

## Comments and Discussions

 First Prev Next
 My vote of 5 long_cloud31-Mar-13 5:56 long_cloud 31-Mar-13 5:56
 Another alternative. Bill Anderson28-Dec-12 13:27 Bill Anderson 28-Dec-12 13:27
 After playing around with the basic sieve algorithm and Alternative #4, it appears there are a lot of attempts to sieve out a number that has already been sieved previously. For example 6. Two sieves it and so does Three. Likewise, 35 is sieved out 2 times, because 5 and 7 are the prime factors of 35. While looking more closely at the sieve process that only touches multiples of 6 +/- 1, it looked like we could minimize (and even remove) the need to sieve out composites multiple times. So I attempted to re-factor Alt. #4. The key is creating a number range with only multiples of 6+/-1, ie: 5,7,11,13...35,37...65,67, etc. Here is the method. ```private static BitArray Sieve(int candidate) { #region CREATE CONTAINER TO SIEVE   BitArray sieveContainer = new BitArray(candidate + 1, false); int totalCyclesOfSix = (int)Math.Floor((double)candidate / 6);   sieveContainer[2] = true; //2 is prime sieveContainer[3] = true; //3 is prime //Create container with only multiples of 6 +/- 1 as potential primes. //We will sieve this container while (totalCyclesOfSix > 0) { sieveContainer.Set(totalCyclesOfSix * 6 - 1, true); sieveContainer.Set(totalCyclesOfSix * 6 + 1, true); totalCyclesOfSix--; }   #endregion   #region PERFORM THE SEIVE   int outerPrimeFactor = 0, innerPrimeFactor = 0, currentPrimeMarker = 5, nextPrimeMarker = 7;   while (currentPrimeMarker * currentPrimeMarker <= candidate) { //Sieve off all multiples of the current prime //i.e.: current prime = 5, canddiate = 1000, then sieve: 5^2,5^3,5^4, and 5^5 outerPrimeFactor = (int)Math.Ceiling(Math.Log((double)candidate, (double)currentPrimeMarker)); innerPrimeFactor = outerPrimeFactor - 1;   while (--outerPrimeFactor > 1) { sieveContainer.Set((int)Math.Pow(currentPrimeMarker, outerPrimeFactor), false); } //After sieving current prime powers out of the candidate value, //we need to sieve those prime powers and product of future primes. //i.e: current prime = 5, candidate = 1000, we need to sieve: //5^2*7, 5^1*7 = 35, 5^2*7 = 175, 5^3*7= 875 while (--innerPrimeFactor > 0) { nextPrimeMarker = currentPrimeMarker; while (!sieveContainer.Get(++nextPrimeMarker)) ;   int factor = (int)Math.Pow(currentPrimeMarker, innerPrimeFactor) * nextPrimeMarker; while (factor <= candidate) { sieveContainer.Set(factor, false); while (!sieveContainer.Get(++nextPrimeMarker)) ; factor = (int)Math.Pow(currentPrimeMarker, innerPrimeFactor) * nextPrimeMarker; } }   //Complete, get the next current prime, make it the current one, and //run the process again while (!sieveContainer.Get(++currentPrimeMarker)) ; }   #endregion   return sieveContainer; } ```
 very nice .. dineshkummarc18-Nov-11 0:31 dineshkummarc 18-Nov-11 0:31
 Reason for my vote of 5 Loved it... GPUToaster™13-Sep-11 0:33 GPUToaster™ 13-Sep-11 0:33
 Reason for my vote of 5 Nice concept... Pravin Patil, Mumbai12-Sep-11 9:21 Pravin Patil, Mumbai 12-Sep-11 9:21
 Edit: Added wiki link to the sieve definition for those who ... DaveAuld11-Sep-11 11:23 DaveAuld 11-Sep-11 11:23
 Re: Edit: Fixed the link Reiss12-Sep-11 1:27 Reiss 12-Sep-11 1:27
 Last Visit: 31-Dec-99 19:00     Last Update: 5-May-15 1:42 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.