Prime Number Sieve of Eratosthenes in C# and VB.NET

The following code implements the in VB (C# is a little further down the page):

Imports System

Imports System.Collections.Generic

Imports System.Text

Imports System.Diagnostics

‘Sieve of Eratosthenes



Public Class PrimeSieve


    Private values As Numbers()


    Public Sub New(ByVal max As Integer)

        ReDim values(max)

    End Sub


    Public Function ComputePrimes() As TimeSpan

        Dim sw As Stopwatch = New Stopwatch

        values(0) = Numbers.Prime

        ‘not really… but, it helps

        values(1) = Numbers.Prime


        ‘Loop through each unset value

        Dim outer As Integer = 2

        Do While (outer <> -1)

            ‘The next unset value must be prime

            values(outer) = Numbers.Prime


            ‘mark out all multiples of this prime as being Composite

            Dim inner As Integer = (outer * 2)

            Do While (inner < values.Length)

                values(inner) = Numbers.Composite

                inner = (inner + outer)


            outer = FirstUnset(outer)



        Return sw.Elapsed

    End Function


    Function FirstUnset(ByVal last As Integer) As Integer

        Dim i As Integer = last

        Do While (i < values.Length)

            If (values(i) = Numbers.Unset) Then

                Return i

            End If

            i = i + 1


        Return -1

    End Function


End Class


Public Enum Numbers





End Enum

Module Module1


    Sub Main()

        Dim ps As PrimeSieve = New PrimeSieve(100000)

        Dim ts As TimeSpan = ps.ComputePrimes

        Console.WriteLine(“Complete: {0}”, ts)


    End Sub

End Module


The following code implements the in C#:

using System;

using System.Collections.Generic;

using System.Text;

using System.Diagnostics;


//Sieve of Eratosthenes

namespace Samples


    public class PrimeSieve : IEnumerable<int>


        Numbers[] values;

        public PrimeSieve(int max)


            values = new Numbers[max];


        public TimeSpan ComputePrimes()


            Stopwatch sw = new Stopwatch();

            values[0] = Numbers.Prime; //not really… but, it helps

            values[1] = Numbers.Prime;



            //Loop through each unset value

            for (int outer = 2; outer != -1; outer = FirstUnset(outer))


                //The next unset value must be prime

                values[outer] = Numbers.Prime;

                //mark out all multiples of this prime as being Composite

                for (int inner = outer*2; inner < values.Length; inner += outer)


                    values[inner] = Numbers.Composite;




            return sw.Elapsed;


        int FirstUnset(int last)


            for (int i = last; i < values.Length; i++)


                if (values[i] == Numbers.Unset) return i;


            return -1;



        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()


            return GetEnumerator();


        public IEnumerator<int> GetEnumerator()


            for (int i = 2; i < values.Length; i++)


                if (values[i] == Numbers.Prime) yield return i;




    public enum Numbers







    class Program



        static void Main(string[] args)


            PrimeSieve ps = new PrimeSieve(100000000);

            TimeSpan ts = ps.ComputePrimes();

            foreach (int i in ps)




            Console.WriteLine(“Complete: {0}”, ts);


            List<int> l = new List<int>();

            int last = 0;

            foreach (int i in ps)


                l.Add(Math.Abs(last – i));

                last = i;



            double sum = 0.0;

            double sumOfSqrs = 0.0;

            l.ForEach(delegate(int value)


                sum += value;

                sumOfSqrs += Math.Pow(value, 2);


            double n = (double)l.Count;

            double topSum = (n * sumOfSqrs) – (Math.Pow(sum, 2));

            double standardDeviation = Math.Sqrt(topSum / (n * (n – 1)));

            Console.WriteLine(“Average: {0:##.##}”, sum / n);

            Console.WriteLine(“Standard Deviation {0}”, standardDeviation);








Comments (3)

  1. David Smith says:

    I’m happy to see people blogging about the new ‘yield’ keyword. =) Very useful for IEnumerable.

  2. I think it’s interesting to contrast this with a Scheme implementation which sets up a general infrastructure for handling infinite streams and then calculates the primes as needed. Why does your C# implementation precalculate the whole list? What would it look like the other way?


    (define-syntax cons-stream

    (syntax-rules ()

    ((cons-stream x y)

    (cons x (delay y)))))

    (define head car)

    (define (tail stream) (force (cdr stream)))

    (define empty-stream? null?)

    (define the-empty-stream ‘())

    (define (sieve stream)


    (head stream)



    (lambda (x) (not (divisible? x (head stream))))

    (tail stream)))))

    (define (divisible? x y)

    (= (remainder x y) 0))

    (define (filter-stream p lst)

    (cond ((empty-stream? lst) the-empty-stream)

    ((p (head lst)) (cons-stream (head lst) (filter-stream p (tail lst))))

    (else (filter-stream p (tail lst)))))

    (define (integers-starting-from n)

    (cons-stream n

    (integers-starting-from (+ n 1))))

    (define primes (sieve (integers-starting-from 2)))