Click here to Skip to main content
12,451,446 members (48,070 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

6.6K views
Posted

Find Prime Numbers in C# Using the Sieve of Eratosthenes

, 20 Sep 2011 CPOL
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)

You may also be interested in...

Pro
Pro

Comments and Discussions

 
Generalso simple and compact very nice .. Pin
dineshkummarc17-Nov-11 23:32
memberdineshkummarc17-Nov-11 23:32 

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.

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