Click here to Skip to main content
15,119,639 members
Articles / Programming Languages / C#
Tip/Trick
Posted 19 Jul 2011

Tagged as

Stats

59.9K views
8 bookmarked

Find Prime Numbers in C# Using the Sieve of Eratosthenes

Rate me:
Please Sign up or sign in to vote.
4.80/5 (5 votes)
3 Oct 2011CPOL
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:

C#
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++)
                        primeCandidates.Add(2*i-1);

                    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
                    outputLines.Add(currentOutputLine);
                }

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

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

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

Comments and Discussions

 
GeneralMy vote of 5 Pin
long_cloud31-Mar-13 5:56
Memberlong_cloud31-Mar-13 5:56 
GeneralAnother alternative. Pin
Bill Anderson28-Dec-12 13:27
MemberBill Anderson28-Dec-12 13:27 
Generalvery nice .. Pin
Denno.Secqtinstien18-Nov-11 0:31
MemberDenno.Secqtinstien18-Nov-11 0:31 
GeneralReason for my vote of 5 Loved it... Pin
GPUToaster™13-Sep-11 0:33
MemberGPUToaster™13-Sep-11 0:33 
Reason for my vote of 5
Loved it...
GeneralReason for my vote of 5 Nice concept... Pin
Pravin Patil, Mumbai12-Sep-11 9:21
MemberPravin Patil, Mumbai12-Sep-11 9:21 
GeneralEdit: Added wiki link to the sieve definition for those who ... Pin
DaveAuld11-Sep-11 11:23
professionalDaveAuld11-Sep-11 11:23 
GeneralRe: Edit: Fixed the link Pin
Reiss12-Sep-11 1:27
professionalReiss12-Sep-11 1:27 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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