14,087,968 members
alternative version

#### Stats

54K views
8 bookmarked
Posted 19 Jul 2011
Licenced CPOL

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

, 3 Oct 2011
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
foreach(string number in numbersList) {
int N = Int32.Parse(number);
List<int> primeCandidates = new List<int>(N);
if (N==2)
{
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);
}
}
}
}```

## Share

 Software Developer (Senior) xyLOGIX, LLC United States
No Biography provided

## You may also be interested in...

 Pro

 First Prev Next
 My vote of 5 long_cloud31-Mar-13 4:56 long_cloud 31-Mar-13 4:56
 Another alternative. Bill Anderson28-Dec-12 12:27 Bill Anderson 28-Dec-12 12:27
 very nice .. Denno.Secqtinstien17-Nov-11 23:31 Denno.Secqtinstien 17-Nov-11 23:31
 Reason for my vote of 5 Loved it... GPUToaster™12-Sep-11 23:33 GPUToaster™ 12-Sep-11 23:33
 Reason for my vote of 5 Nice concept... Pravin Patil, Mumbai12-Sep-11 8:21 Pravin Patil, Mumbai 12-Sep-11 8:21
 Reason for my vote of 5 Nice concept...
 Edit: Added wiki link to the sieve definition for those who ... DaveAuld11-Sep-11 10:23 DaveAuld 11-Sep-11 10:23
 Re: Edit: Fixed the link Reiss12-Sep-11 0:27 Reiss 12-Sep-11 0:27
 Last Visit: 19-May-19 9:21     Last Update: 19-May-19 9:21 Refresh 1