Threshed and Malachi'd: Sieve of Eratosthenes I took a little bit from all the answers to my previous question Threshing: Sieve of Eratosthenes.



This may be bordering on code-golfing, but I think that I have a pretty good piece of code here.

Is there any major concepts that I am overlooking, although it still seems super simple?

var upperLimit = 9999;
var primes = new List&lt;long&gt;();
primes.Add(1);
primes.Add(2);
for (var i = 3; i &lt; upperLimit; i+=2)
{
    primes.Add(i);
}

for (var i = 7; i &lt; upperLimit; i+=2)
{
    foreach (var number in primes.ToList())
    {
        if (number == i) { continue; }
        if (number % i == 0) { primes.Remove(number); }
    }
}
primes.ForEach(Console.WriteLine);
Console.WriteLine("The Last Prime is " + primes[primes.Count - 1]);
Console.WriteLine("what are you waiting for? Exit the program!");


Obviously I could start off with all the primes I know by just adding them to start with and then starting my loops higher, but I think that is cheating just a little bit.

Is there any way to make this faster and able to calculate (and store) higher numbers using less memory?
This line here is horrible, terrible, and miserable:


if (number % i == 0) { primes.Remove(number); }



That one line is basically (behind the scenes) doing the following:


scan all the data from the beginning until you find the member with the value number
if you find that value:

for every remaining value, shift it one back (replace each n with the value at n + 1).
shrink the size of the List by 1.



The above is an \$O(n)\$ operation.

Using an indexed method to remove the value would be much faster, and a data structure like a Linked list with a \$O(1)\$ remove, would make a huge difference.