Sprache: VB
Diese Funktion berechnet alle Primzahlen < n.
Als Optimierung habe ich gerade Zahlen übersprungen.
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_des_Eratosthenes
[u]Sieve of Eratos.[/u]: 664579 primes < 10^7 computed in [b]00:01.3361552[/b]
[u]Sieve of Eratos.[/u]: 5761455 primes < 10^8 computed in [b]00:23.7904888[/b]
mm:ss.ms
[b]Zum Vergleich[/b]: http://dotnet-snippets.de/dns/effizientere-primzahlpruefung-grosser-zahlen-SID1373.aspx
Sub eratos(ByVal l As Integer)
Dim primes(l) As Boolean
For i As Integer = 3 To Math.Sqrt(l) Step 2
For j As Integer = i * i To l Step i
primes(j) = True
Next
Next
Console.WriteLine(2)
For i = 3 To l Step 2
If Not primes(i) Then Console.WriteLine(i)
Next
End SubSub eratos(ByVal l As Integer)
Dim primes(l) As Boolean
For i As Integer = 3 To Math.Sqrt(l) Step 2
For j As Integer = i * i To l Step i
primes(j) = True
Next
Next
Console.WriteLine(2)
For i = 3 To l Step 2
If Not primes(i) Then Console.WriteLine(i)
Next
End Sub
Alte URL:
/snippet/das-sieb-des-eratosthenes/1379
Deine Bemühungen in allen Ehren aber guck dir mal diesen Post an http://forum.byte-welt.net/showpost.php?p=12074&postcount=26 <-- Post 26 & 27 Der ist umgerechnet fast 10x so schnell wie dein Programm. Wollts nur gesagt habn [b]trotzdem guter Code ;-)[/b]
Das Sieb von Atkin ist eine Optimierung des Sieb des Eratosthenes. Auch das wird bald als Snippet von mir hier veröffentlicht.
Hier das versprochene Snippet.
http://dotnet-snippets.de/dns/das-sieb-von-atkin-SID1426.aspx
Der Code wurde sichtlich entschlankt. Durch Verwendung eines Arrays anstatt einer Liste entfallen das Hinzufügen aller boolschen Werte und das Negieren jener geraden.
Die While-Schleife wurde durch eine For-Schleife ersetzt, was ebenfalls ein paar Zeilen einspart.