HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Threshing: Sieve of Eratosthenes

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
sievethreshingeratosthenes

Problem

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 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 primes = new List();
    for (Int64 i = 2; i  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

Solution

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 primes = new List();    
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.

Code Snippets

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

Context

StackExchange Code Review Q#56500, answer score: 6

Revisions (0)

No revisions yet.