Click here to Skip to main content
Click here to Skip to main content
Alternative Tip

Tagged as

Go to top

Find Prime Numbers in C# Using the Sieve of Eratosthenes

, 20 Sep 2011
Rate this:
Please Sign up or sign in to vote.
This solution uses half the space by simply ignoring all even numbers. It will require a little index calculation. Also, primes are generated one by one instead of returning a list.Another optimization can be made by starting the crossing out of multiples of a prime p at p2. Any smaller number...

This solution uses half the space by simply ignoring all even numbers. It will require a little index calculation. Also, primes are generated one by one instead of returning a list.

Another optimization can be made by starting the crossing out of multiples of a prime p at p2. Any smaller number will already have been crossed out. For the same reason, we can stop looking for non-primes at Sqrt(bound). (Any number greater than that will have been crossed out as a multiple of a smaller number.)

public static IEnumerable<int> Primes(int bound)
{
    if (bound < 2) yield break;
    //The first prime number is 2
    yield return 2;
 
    //Create a sieve of 'half size' starting at 3
    BitArray notPrime = new BitArray((bound - 1) >> 1);
    int limit = ((int)(Math.Sqrt(bound)) - 1) >> 1;
    for (int i = 0; i < limit; i++) {
        if (notPrime[i]) continue;
        //The first number not crossed out is prime
        int prime = 2 * i + 3;
        yield return prime;
        //cross out all multiples of this prime, starting at the prime squared
        for (int j = (prime * prime - 2) >> 1; j < notPrime.Count; j += prime) {
            notPrime[j] = true;
        }
    }
    //The remaining numbers not crossed out are also prime
    for (int i = limit; i < notPrime.Count; i++) {
        if (!notPrime[i]) yield return 2 * i + 3;
    }
}

License

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

Share

About the Author

Dennis_E
Software Developer (Junior)
Netherlands Netherlands
Software developer with a bachelor degree and a few years experience (studied computer science at a university as well, but didn't finish). Really love C#, but work usually involves Java. Some experience with VB and C as well.
 
When hobbying I almost exclusively use C# and AutoHotkey. In a previous life I did some Haskell and Modula-3 and similar stuff. I enjoy games and solving puzzles like on http://projecteuler.net/ (I think I'm stuck at level 4, though)

Comments and Discussions

 
Generalso simple and compact very nice .. Pinmemberdineshkummarc17-Nov-11 23:32 

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

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

| Advertise | Privacy | Mobile
Web02 | 2.8.140916.1 | Last Updated 20 Sep 2011
Article Copyright 2011 by Dennis_E
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid