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

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)

{

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

}

}

}

Tags

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 (tail stream) (force (cdr stream)))

(define empty-stream? null?)

(define the-empty-stream ‘())

(define (sieve stream)

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