Generate Prime Numbers via Eratosthene's Sieve C#

Question

I'm attempting to solve Question 3 for Project Euler, found here. I would like to solve it by generating a List of Primes using Eratosthene's Sieve (found here. I'm nowhere near finishing the question, but I have run into a small problem...

Below is my code I have worked on for doing so. However, when I run this code, it stalls my computer, and outputs a 2 before stalling it some more. It is obviously running, however it doesn't seem to be doing it right. Before it outputs the list, it should let me know (just checking if the hangup is before output) it is done allocating the list...

If you aren't sure what is going on, can you give me pointers for digging into the code and debugging its different lines? I've tried Console.WriteLine in different areas, but it doesn't seem to respond to the code.

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    static void Main(string[] args)
    {
        long maxNum = 100;
        double maxSqrt = Math.Floor(Math.Sqrt(maxNum));
        long basePrime;
        // Make a list from 2 to maxNum
        List<long> numberList = new List<long>();
        List<long> sievedList = new List<long>();
        for (long i = 2; i <= maxNum; i++) numberList.Add(i);
        // Evaluate the first number of the list, if it is < maxSqrt skip it, create a list of multiples and Except them from numberList, else, numberList is completely Prime Factors

        foreach (long number in numberList.Skip(1))
        {
            basePrime = numberList[0];
            Console.WriteLine(basePrime);
            while (number < maxSqrt)
                {
                    if (number % basePrime == 0)
                    {
                        sievedList.Add(number);
                    }
                    numberList = numberList.Except(sievedList).ToList();
                    sievedList.Clear();
                }
        }
    Console.WriteLine("Finished Allocating Primes");   
    numberList.ForEach(Console.WriteLine);
    }
}

Answer 1

Inspired By: Laziness in Python - Computerphile Which I translated to C#:

using System;
using System.Collections.Generic;
using System.Linq;

namespace GenertatorTest
{
    class Program
    {
        /// <summary>
        /// Natural Numbers Genarator
        /// </summary>
        /// <param name="first">first number in the sequence</param>
        /// <returns>the sequence: first, first + 1, first + 2, ... ∞</returns>
        static IEnumerable<int> natural(int begin)
        {
            yield return begin;
            foreach (var item in natural(begin + 1))
            {
                yield return item;
            }
        }

        /// <summary>
        /// Primary Numbers Genarator
        /// </summary>
        /// <param name="nums">natural numbers sequence which we want to apply  Eratosthene's Sieve on</param>
        /// <returns>infinite primary numbers sequence</returns>
        static IEnumerable<int> primes(IEnumerable<int> nums)
        {
            int p = nums.ElementAt(0);
            yield return p;
            foreach (var item in primes(nums.Where(x => x % p != 0)))
            {
                yield return item;
            }
        }

        static void Main(string[] args)
        {
            foreach (var item in primes(natural(2)))
            {
                Console.WriteLine(item);
                //it is infinite sequence
                //so you cant just run through. 
                Console.ReadKey();
            }
        }
    }
}

Actually this Code is more elegant than you think. the only syntax sugar we lack here is yield from, which seems to be not supported in C#.

Answer 2

For your immediate problem, change the while to an if.

However your code has other problems as well.

• Your numberedList is just a list of integers from 2 to maxNum that you're populating with a for loop. Then you're iterating through the list. Just use the counter from the for loop, instead. To keep a record of which numbers are prime, a BitArray(Int32, Boolean) works well.
• That also allows to get rid of the expensive LINQ extensions. When you find a non-prime number just change it's index in the BitArray. When you find a prime number add it to the list;