# Threshing: Sieve of Eratosthenes

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++)
{
}
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!");
}


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

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++)


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

• why the fancy 2*x-1 and x <= (upperLimit+1)/2 what does it do? I just added 1 and 2 to the list and then started at 3 and incremented by 2 – Malachi Jul 9 '14 at 18:34
• @Malachi - It limits all entries to odd numbers. Any even number greater than 2 is automatically non prime. So, if the number is 9999, we go from 1 to 5000, multiply each number by 2 to make it even and subtract one. This gives us a list of all odd numbers, which reduces the iterations through the sieve. – JohnP Jul 9 '14 at 18:37
• so the same as int i = 3; i<upperLimit; i+=2 and primes.Add(i) ? – Malachi Jul 9 '14 at 18:40
• In effect, yes. .netfiddle theoretically says this uses less memory, but it's erratic on that so... – JohnP Jul 9 '14 at 18:57

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);


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++)

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!");
}


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.

• it won't run unless you use filtered.ToArray() in the foreach loop, otherwise I have to rewrite to use a backwards for loop – Malachi Jul 9 '14 at 15:03
• I think this is going to be less efficient, because it looks as though it will actually run 2 loops, 1 for the filtered variable, and one to remove the number. Even though it is nice fancy LINQ query and I like it, it is still going to run a foreach on the list. – Malachi Jul 9 '14 at 15:10
• If you're definitely getting bad performance, that's worth considering. Also, I don't think you do need .ToArray(), because it's a different collection. Mostly, I'd suggest trying it first. – Magus Jul 9 '14 at 16:21
• Ah, I see, it does need to be run, or else it counts as the same collection. Overall, I find it to be incredibly fast. – Magus Jul 9 '14 at 16:24

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)));
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());
}
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++)
{
}
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);
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.

• When I plugged in your code and my code into .NET Fiddle. it turns out that my code runs faster and uses less Memory when the upperLimit is set to int.MaxValue – Malachi Jul 9 '14 at 18:29
• @Malachi - There must something wrong with the way you're comparing the 2 codes. Even on only 1000 as the upperlimit your code takes over 8 seconds compared to a less that 50 milliseconds for the code I showed you. – tinstaafl Jul 9 '14 at 20:32
• try it the other way around (mine second, yours first) and see what happens? I am working on something at work at the moment, but will check it out when I get a chance – Malachi Jul 9 '14 at 20:37
• Same basic result – tinstaafl Jul 9 '14 at 20:39
• huh? that is weird, we have seen some weird results from netfiddle. it was definitely harder to read your code overall, but I will look at it more closely when I get a chance. – Malachi Jul 9 '14 at 20:59