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