Threshing: Sieve of Eratosthenes

Question

I would like a complete threshing of this code so that I can see what I did wrong and what I am using incorrectly.

I made this super simple, trying to learn a little bit about List<T> while I was doing this. I have never actually tried to do this before, so I thought it would be a good learning experience, but it just seems too easy (simple), especially when I look at other people's renditions of this algorithm. Am I missing a vital piece of the algorithm?

Note: Console app, if you want to see all the primes you will have to set the buffer of your console.

static void Main(string[] args)
{
    var upperLimit = 9999;
    List<Int64> primes = new List<Int64>();
    for (Int64 i = 2; i < upperLimit; i++)
    {
        primes.Add(i);
    }
    List<Int64> numbers = primes;

    for (var i = 2; i < upperLimit; i++)
    {     
        foreach (var number in numbers.ToArray())
        {
            if (number == i) { continue; }
            if (number % i == 0)
            {
                primes.Remove(number);
            }
        }
        numbers = primes;
    }
    primes.ForEach(delegate(Int64 prime)
    {
        Console.WriteLine(prime.ToString());
    });

    Console.WriteLine("The Last Prime is " + primes[primes.Count - 1]);
    Console.WriteLine("what are you waiting for? Exit the program!");
    Console.ReadLine();
}

---

I figured that I would give this a try after I saw this.

---

The reason for var number in numbers.ToArray() is because it wouldn't let me .Remove(number) from primes if I foreach'ed through the list otherwise. Credit to this answer for the solution to my dilemma.

---

Follow-up can be found here

Answer 1

One note: You create extra work and time for the program by including all of the even numbers in the initial List creation.

You can do something similar to this to eliminate the even numbers:

var upperLimit = 9999;
List<Int64> primes = new List<Int64>();    
for (int x = 2; x <= (upperLimit+1)/2; x++)
    primes.Add(2*x-1);

That should give you a much reduced list to have to run through. Other than that, it's a very nice and simple solution.

Answer 2

The algorithm seems okay (but inefficient), but a few remarks about the code:

You're using Int64. This is totally unnecessary. upperLimit is an Int32 and you won't be able to store that many numbers in the List anyway.

You are storing every number up to upperLimit. With 9999 this is fine, but suppose someone were to set upperLimit to int.MaxValue (2^31). This would require 8Gb of memory. (And you're doing ToArray(), which will at least double the space). A BitArray will only store 1 bit of information for each number instead of 4 bytes (when using Int32) or 8 bytes (if using Int64)

The numbers variable also looks unnecessary. You're just letting it reference the same array as primes. To avoid having to do ToArray(), you can use a regular for-loop. You need to loop from end to start, though.

for (int i = 2; i < upperLimit; i++) {
    for (int j = primes.Count - 1; j >= 0; j--) {
        int number = primes[j];
        if (number == i) continue;
        if (number % i == 0) {
            primes.RemoveAt(j); //Remove the item at index j
            //primes.Remove(number) will search the entire list for number.
        }
    }
}

The delegate syntax can be a lot simpler:

primes.ForEach(Console.WriteLine);

Answer 3

Generally speaking, this seems fine.

The main changes I'd make are to change the Int64 to long which has the same meaning, but is more comfortable for users of other languages. It's very rare to see a style standard that does the opposite.

I'd also make your upper limit constant, and move your filtering out of the foreach. Additionally, List<T>.ForEach(...) is considered bad form, because it modifies a collection rather than yielding one.

I indent well, and so I don't worry about including parentheses as much as some style guides recommend. In my eyes, stupid has no cure.

I've included my version of the code.

static void Main(string[] args)
{
    const int upperLimit = 9999;
    var primes = new List<long>();
    for (long i = 2; i < upperLimit; i++)
        primes.Add(i);

    var numbers = primes;

    for (var i = 2; i < upperLimit; i++)
    {
        var filtered = numbers.Where(number => number != i && number % i == 0).ToList();
        foreach (var number in filtered)
            primes.Remove(number);

        numbers = primes;
    }
    foreach (var prime in primes)
        Console.WriteLine(prime.ToString());

    Console.WriteLine("The Last Prime is " + primes[primes.Count - 1]);
    Console.WriteLine("what are you waiting for? Exit the program!");
    Console.ReadLine();
}

EDIT: Added .ToList() to evaluate the filter and ensure that it is a separate collection, rather than a query.

Note that this answer purely regards code quality, not efficiency. Other answers appear to address efficiency well enough - but this still runs pretty much instantly on my machine, so optimization may not be in order.

Answer 4

As was mentioned a BitArray initialized to the size needed and initialized to true, eliminates filling the collection with numbers. Basically turn an element off if the index is a composite number. For building a list of prime numbers, using an offset reduces the size of the array and speeds up the code considerably:

public List<int> ESieve(int upperLimit)
{
    int sieveBound = (int)(upperLimit - 1) / 2;
    int upperSqrt = ((int)Math.Sqrt(upperLimit) - 1) / 2;
    BitArray PrimeBits = new BitArray(sieveBound + 1, true);
    List<int> numbers = new List<int>((int)(upperLimit / (Math.Log(upperLimit) - 1.08366)));
    numbers.Add(2);
    for(int i = 1; i <= upperSqrt; i++)
    {
        if(PrimeBits.Get(i))
        {
            numbers.Add(2 * i + 1);
            for(int j = i * 2 * (i + 1); j <= sieveBound; j += 2 * i + 1)
            {
                PrimeBits.Set(j, false);
            }
        }
    }


    for(int i = upperSqrt + 1; i <= sieveBound; i++)
    {
        if(PrimeBits.Get(i))
        {
            numbers.Add(2 * i + 1);
        }
    }

    return numbers;
}

When I compare both codes side by side in .netFiddle or on my own computer, you code is about 100 times slower. Here's the code I used:

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TestPrimeList
{
    public class Program2
    {
        public static void Main(string[] args)
        {

            long result = 41;
            int iter = 1;
            //long i = 0;
            var t2 = Measure(iter, () =>
            {
                List<Int64> primelist2 = ESieve(1000);
                result = primelist2.Length;
            });
            Console.WriteLine("result  - " + result + " || " + new TimeSpan(t2.ElapsedTicks / iter).TotalMilliseconds.ToString());
            long result2 = 0;
            var t3 = Measure(iter, () =>
            {
                List<Int64> primelist = ESieve1(1000);
                result2 = primelist.Length;
            });
            Console.WriteLine("result2 - " + result2 + " || " + new TimeSpan(t3.ElapsedTicks / iter).TotalMilliseconds.ToString());
            Console.ReadLine();
        }
        public static Stopwatch Measure(int n, Action action)
        {
            action();
            var sw = Stopwatch.StartNew();
            for (; n > 0; n--)
                action();
            sw.Stop();
            return sw;
        }
        public static List<Int64> ESieve(int upperLimit)
        {
            List<Int64> primes = new List<Int64>();
            for (Int64 i = 2; i < upperLimit; i++)
            {
                primes.Add(i);
            }
            List<Int64> numbers = primes;

            for (var i = 2; i < upperLimit; i++)
            {
                foreach (var number in numbers.ToArray())
                {
                    if (number == i) { continue; }
                    if (number % i == 0)
                    {
                        primes.Remove(number);
                    }
                }
                numbers = primes;
            }
            return numbers;
        }
        public static List<Int64> ESieve1(int upperLimit)
        {
            int sieveBound = (int)(upperLimit - 1) / 2;
            int upperSqrt = ((int)Math.Sqrt(upperLimit) - 1) / 2;
            BitArray PrimeBits = new BitArray(sieveBound + 1, true);
            List<Int64> numbers = new List<Int64>((int)(upperLimit / (Math.Log(upperLimit) - 1.08366)) + 4);
            numbers.Add(2);
            for (int i = 1; i <= upperSqrt; i++)
            {
                if (PrimeBits.Get(i))
                {
                    numbers.Add(2 * i + 1);
                    for (int j = i * 2 * (i + 1); j <= sieveBound; j += 2 * i + 1)
                    {
                        PrimeBits.Set(j, false);
                    }
                }
            }


            for (int i = upperSqrt + 1; i <= sieveBound; i++)
            {
                if (PrimeBits.Get(i))
                {
                    numbers.Add(2 * i + 1);
                }
            }

            return numbers;
        }
    }
}

To keep things as quick as possible I only compare the length's of the returned collection.