素数判定～エラトステネスの篩～

こないだうちの会社の入社試験で簡単なプログラムを出題されてましたが、こういうのってなかなか自分から書こうと思わないですよね。
たまには、こういう頭の体操をして純粋にプログラムを楽しむのもいいと思います。
って事でちょうど気分転換に良さそうな素数判定を書いてみようと思います。
素数判定のアルゴリズムは、えらい学者さんが考案したとされるエラトステネスの篩を使います。
Wikipediaの通り実装すると下記の通り。（２，３の倍数は、探索リストから除外してますが）
実行環境
言語：vb.net 2010 .net fremework 4.0 CP
OS:XP

Sub Main()
    Dim sw As New Stopwatch

    sw.Start()
    '判定結果格納用
    Dim lst As New Dictionary(Of Integer, Integer)
    '探索リスト
    Dim src As New Dictionary(Of Integer, Integer)

    '2，3を探索リストから除外する
    src.Add(2, 2)
    src.Add(3, 3)
    '1000万までの2，3の倍数以外を探索リストに追加する。
    For i As Integer = 3 To 10000000 Step 2
        If i Mod 3 > 0 Then
            src.Add(i, i)
        End If
    Next
    '5（3以降の最初の素数）を判定値にエラトステネスのふるいにかける。
    eratosutenesu(5, lst, src)
    sw.Stop()
    Console.WriteLine("判定:" & sw.Elapsed.ToString)
    '1～1000万に含まれる素数の数は、664579個
    Console.WriteLine(lst.Count & "件")
    Console.ReadLine()

End Sub

Private Sub eratosutenesu(value As Integer, lst As Dictionary(Of Integer, Integer), src As Dictionary(Of Integer, Integer))

    '探索リストの最大値を取得する。
    Dim max As Integer = src.Keys(src.Count - 1)

    '判定値の約数を全て探索リストからさ駆除する。
    For i As Integer = value To max Step value
        If src.ContainsKey(i) Then
            src.Remove(i)
        End If
    Next
    lst.Add(value, value)
    '探索リストの最大値より判定値の平方根が小さい場合は処理終了
    'それ以外は再帰し、再度ふるいにかける。
    If value ^ 2 < src.Keys(src.Count - 1) Then
        eratosutenesu(src.Keys(0), lst, src)
    Else
        '上記以外は、残りの素数判定リストは、全て素数
        For Each i As Integer In src.Keys
            lst.Add(i, i)
        Next
    End If
End Sub

最初は、Listで実装したのですが、削除がとてつもなく遅かったので、Dictionaryで実装しました。
それでも１０００万件の素数判定で、３０秒以上掛かります。（まだまだですね・・・
探索リストをもう少し絞れば、早くなりそうですが、それは、また別の機会に。