Option Strict On
 
Imports System
Imports System.Console
Imports System.Collections
Imports System.Environment
 
Public Class Main
 
  Shared Sub Main()
    Dim MaxValue, Runs As Integer
    Dim Times As Integer()
    Dim i As Integer
 
    WriteLine("****************")
    WriteLine("*  Primzahlen  *")
    WriteLine("****************")
    WriteLine()
 
    Write("Berechnen bis: ")
    MaxValue = Integer.Parse(ReadLine())
 
    Write("Durchläufe: ")
    Runs = Integer.Parse(ReadLine()) - 1
 
    ReDim Times(Runs)
 
    WriteLine()
 
    For i = 0 To Runs
      Write("{0}. Durchlauf: ", (i + 1).ToString("0"))
      Times(i) = GetPrim(MaxValue)
      WriteLine("{0} ms", Times(i).ToString("#,##0").PadLeft(7, " "c))
    Next
 
    WriteLine()
 
    Dim dTimes As Integer
 
    For i = 0 To Runs
      dTimes += Times(i)
    Next
 
    WriteLine("Durchschnitt: {0} ms", CInt(dTimes \ (Runs + 1)).ToString( _
      "#,##0").PadLeft(7, " "c))
    ReadLine()
 
  End Sub
 
  Private Shared Function GetPrim(ByVal MaxValue As Integer) As Integer
    Dim Start As Integer
 
    Dim Prims As BitArray
    Dim P, i As Integer
 
    Start = TickCount
 
    Prims = New BitArray(MaxValue)
 
    Prims(0) = True
    Prims(1) = True
 
    For i = 4 To MaxValue Step 2
      Prims(i) = True
    Next i
 
    For P = 3 To MaxValue Step 2
      If Not Prims(P) Then
        For i = 2 * P To MaxValue Step P
          Prims(i) = True
        Next i
      End If
 
      If P * P > MaxValue Then
        Exit For
      Else
        P *= P
      End If
    Next
 
    Prims.Clear()
    Prims = Nothing
 
    Return TickCount - Start
 
  End Function
 
End Class
 
Public Class BitArray
 
  Private aBits As Integer()
  Private Const ElementLength As Integer = 32
 
  Sub New(ByVal Length As Integer)
 
    Dim i As Integer
    Dim RealLength As Integer
 
    RealLength = Length \ ElementLength
 
    ReDim aBits(RealLength)
 
  End Sub
 
  Default Public Property Item(ByVal Index As Integer) As Boolean
    Get
      Dim BigIndex As Integer = Index \ ElementLength
      Dim SmalIndex As Integer = 1I << (Index Mod ElementLength)
 
      Return (aBits(BigIndex) And SmalIndex) <> 0
    End Get
    Set(ByVal Value As Boolean)
      Dim BigIndex As Integer = Index \ ElementLength
      Dim SmalIndex As Integer = 1I << (Index Mod ElementLength)
 
      If Value Then
        aBits(BigIndex) = aBits(BigIndex) Or SmalIndex
      Else
        aBits(BigIndex) = aBits(BigIndex) And (Not SmalIndex)
      End If
    End Set
  End Property
 
  Sub Clear()
    Array.Clear(aBits, 0, aBits.Length)
  End Sub
 
End Class

  2.000.000    28 ms
 20.000.000   281 ms
200.000.000 2.828 ms