Das Sieb von Atkin – dotnet-snippets.de

Sprache: VB

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 [u]Atkin[/u]: 664579 primes < 10^7 computed in [b]00:00.4543314[/b] [u]Atkin[/u]: 5761455 primes < 10^8 computed in [b]00:05.1131710[/b] mm:ss.ms [b]Zum Vergleich:[/b] 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

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

Abgelegt unter Atkin check eratosthenes Math Mathe Mathematik number prime Primzahl proof prüfen Sieb sieve Zahl

Alte URL: /snippet/das-sieb-von-atkin/1426

2 Kommentare

Klemens Nanni sagt:

August 6, 2010 um 6:08 p.m. Uhr

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 sagt:

August 12, 2010 um 9:47 p.m. Uhr

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.