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


        sw.Start()


        ‘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


            Console.WriteLine(outer)


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


            Loop


            outer = FirstUnset(outer)


        Loop


        sw.Stop()


        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


        Loop


        Return -1


    End Function


 


End Class


 


Public Enum Numbers


 


    Unset


    Prime


    Composite


End Enum


Module Module1


 


    Sub Main()


        Dim ps As PrimeSieve = New PrimeSieve(100000)


        Dim ts As TimeSpan = ps.ComputePrimes


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


        Console.ReadLine()


    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;


 


            sw.Start();


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


                }


            }


            sw.Stop();


            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


    {


        Unset,


        Prime,


        Composite,


    }


 


    class Program


    {


 


        static void Main(string[] args)


        {


            PrimeSieve ps = new PrimeSieve(100000000);


            TimeSpan ts = ps.ComputePrimes();


            foreach (int i in ps)


            {


                Console.WriteLine(i);


            }


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


            Console.ReadLine();


        }


    }


}


 


 


 

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?

    <http://www.cs.auc.dk/~normark/prog3-03/html/notes/eval-order_themes-delay-stream-section.html&gt;

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

    (cons-stream

    (head stream)

    (sieve

    (filter-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)))