Eratasthenes Sieve

Posted on: April 30, 2016 6:58:52 PM

Another programming challenge was to determine the 5000th prime number. A common way to quickly calculate prime numbers is using a sieve. There are several that you can choose from, I chose to implement Eratasthenes sieve. The code below will allow you to get all the prime numbers up to a limit.

    public class EratosthenesSieve
    {
        public static IEnumerable PrimeNumbers(int limit)
        {
            // add 1 to the limit to determine the limit number itself as well
            BitArray bitArray = new BitArray(limit + 1, true);

            bitArray[0] = false;
            bitArray[1] = false;
            bitArray[2] = true;

            yield return 2;

            for (int i = 4; i < bitArray.Length; i += 2)
            {
                bitArray[i] = false;
            }

            for (int i = 3; i < bitArray.Length; i++)
            {
                if (bitArray[i])
                {
                    yield return i;

                    for (int x = i * 2; x < bitArray.Length; x += i)
                    {
                        bitArray[x] = false;
                    }
                }
            }
        }
    }

Comments


Interesting way of doing it, I like the deferred execution.

Jake May 2, 2016 11:48:27 PM

[url=https://vslevitrav.com/]salzarex vardenafil[/url]

fishath March 17, 2021 10:17:14 AM

[url=https://fcialisj.com/]tadalafil cialis from india[/url]

fishath March 20, 2021 6:24:31 PM

Leave a Comment