Feedback

VB - Das Sieb von Atkin

Veröffentlicht von am 8/5/2010
(0 Bewertungen)
Diese Funktion berechnet alle Primzahlen < n. Sie ist eine erweiterte Form des Siebes des Eratosthenes. Für Grenzwerte < 10^6 ist das S.v.A. minimalst langsamer, wohingegen der Vorsprung für größere Werte immer größer wird.

Alternativ können die gefundenen Zahlen auch in einer Liste gespeichert werden, welche dann zurückgegeben wird.

Mehr zum Sieb: http://de.wikipedia.org/wiki/Sieb_von_Atkin

Atkin: 664579 primes < 10^7 computed in 00:00.4543314

Atkin: 5761455 primes < 10^8 computed in 00:05.1131710

mm:ss.ms

Zum Vergleich: http://dotnet-snippets.de/dns/das-sieb-des-eratosthenes-SID1379.aspx
Sub atkin(ByVal l As Integer)
    Dim primes(l) As Boolean, x2 As Integer = 0, y2 As Integer = 0, i As Integer = -1

     For x As Integer = 1 To Math.Sqrt((l - 1) / 2)
        i += 2
        x2 += i

        Dim j As Integer = -1
        For y As Integer = 1 To Math.Sqrt(l - 1)
            j += 2
            y2 += j
            Dim n As Integer = (x2 << 2) + y2

            'Wenn n = 4x²+y² > l, sind weitere Vergleiche unnötig
            If n Mod 2 = 1 AndAlso n <= l Then 'Gerade Zahlen werden übersprungen
                If n Mod 12 = 1 OrElse n Mod 12 = 5 Then primes(n) = Not primes(n) '4x²+y²

                n -= x2
                If n Mod 12 = 7 Then primes(n) = Not primes(n) '3x²+y²

                If x > y Then
                    n -= y2 << 1
                    If n Mod 12 = 11 Then primes(n) = Not primes(n) '3x²-y²
                End If

            Else
                n -= x2
                If n Mod 2 = 1 Then 'gerade Zahlen werden übersprungen
                    If n <= l Then
                        If n Mod 12 = 7 Then primes(n) = Not primes(n) '3x²+y²

                        If x > y Then
                            n -= y2 << 1
                            If n Mod 12 = 11 Then primes(n) = Not primes(n) '3x²-y²
                        End If

                    ElseIf x > y Then
                        n -= y2 << 1
                        If n <= l AndAlso n Mod 12 = 11 Then primes(n) = Not primes(n) '3x²-y²
                    End If
                End If
            End If
        Next
        y2 = 0
    Next

    Console.WriteLine(2 & vbNewLine & 3)
    Dim l_sqrt As Integer = Math.Sqrt(l)

    For x As Integer = 5 To l_sqrt Step 2
        If primes(x) Then
            Dim x22 As Integer = x * x
            For y As Integer = x22 To l Step x22
                primes(y) = False
            Next
            Console.WriteLine(x)
        End If
    Next

    If l_sqrt Mod 2 = 0 Then l_sqrt += 1
    For x As Integer = l_sqrt To l Step 2
        If primes(x) Then Console.WriteLine(x)
    Next
End Sub

2 Kommentare zum Snippet

Klemens Nanni schrieb am 8/6/2010:
Durch das Auslagern der Berechnung x2 in die äußere Schleife, dessen Limit verkleinert wurde, konnte ich den Algorithmus nochmals optimieren. Die Zeiten wurden aktualisiert.
Klemens Nanni schrieb am 8/12/2010:
Durch das Verwenden eines Arrays anstelle einer Liste und das Umstrukturieren der Bedingungen, welches die Anzahl der Abfragen n <= l minimiert, wurde die Arbeiszeit signifikant gekürzt. Die Zeiten wurden aktualisiert.
 

Logge dich ein, um hier zu kommentieren!