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
Abgelegt unter
Primzahl,
prime,
Sieb,
sieve,
Eratosthenes,
Atkin,
prüfen,
proof,
check,
Zahl,
number,
Mathematik,
Mathe,
math.
2 Kommentare zum Snippet