Hi,
2 weitere "langsame" Funktionen...
Beide nutzen komprimierte Siebe, leider kann man mit AutoIt damit keinen Blumenpott gewinnen...(Nicht die Schuld von AutoIt, wer mit einem Ferrari zum Einkaufen fährt und sich über den mangelnden Platz für die 4 Kisten Bier beschwert ist selbst schuld^^)
Das "Sieb von Atkin" u.A. ist eine sehr schnelle Implementation zur Ermittlung großer Primen.
Bei anderen Wettbewerben zur Primzahlbestimmung habe ich festgestellt, daß die "Geschwindigkeit" nicht für die gesamte Laufzeit, sondern für die verschiedenen Bereiche des Programms ausgewertet wird, für z.B. Initialisierung, Primzahlbestimmung (Filterung/Berechnung) und der Ausgabe der Zahlen....egal, es hat mir jedenfalls richtig Spass gemacht! 
Beispiel für komprimiertes Sieb:
In Assembler gibt es eine wesentlich schnellere Alternative zu MOD und Division, wenn der Teiler (hier bei uns wird durch 30 geteilt) bekannt ist. Da auch relativ wenig Speicher erforderlich ist, können die Siebe im Cache liegen und extrem schnell abgearbeitet werden.
Spoiler anzeigen
#include <String.au3>
#include <Array.au3>
;Sieb von Eratosthenes, komprimiert
;
Global $z
Global $limit = 1299709 ;alle Primzahlen bis zum Limit finden
$arraysize = (Int($limit / 30) + 1) * 8 ;Array zur Aufnahme der möglichen Primzahlen, alle Vielfachen von 2,3 und 5 werden nicht berücksichtigt
Dim $a[$arraysize]
;der Vorteil ist, man braucht nur 1/4 des Speicherplatzes für das Sieb
;es werden in diesem komprimierten Sieb alle Vielfachen von 2,3 und 5 nicht berücksichtigt, daraus ergibt sich eine "Matrix" mit möglichen Primzahlen
;Zahlen Spalte
; 0 1 2 3 4 5 6 7
;Zeile
;0 1 7 11 13 17 19 23 29 in dieser Zeile stehen die Spaltenindizes
;1 31 37 41 43 47 49 53 59
;2 61 67 71 73 77 79 83 89
;3 91 97
; Formel zur Berechnung der möglichen Primzahlen:
; Prim = Zeilenanzahl * 30 + Spaltenindex Spaltenindex(0)=1 usw...
Dim $spaltenindex[8] ;
$spaltenindex[0] = 1
$spaltenindex[1] = 7
$spaltenindex[2] = 11
$spaltenindex[3] = 13
$spaltenindex[4] = 17
$spaltenindex[5] = 19
$spaltenindex[6] = 23
$spaltenindex[7] = 29
;dann folgt ein Array, in dem die Spaltenindizes(+1) den Primzahlen von 0-30 zugeordnet werden
Dim $b[31] = [0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 4, 0, 0, 0, 5, 0, 6, 0, 0, 0, 7, 0, 0, 0, 0, 0, 8, 0]
;jede Vielfache der Primzahl soll aus der Matrix eliminiert werden, in der Matrix stehen aber nur Vielfache der Primen von 7 bis 29
;also wird nur die Zahl aus der Matrix eliminiert, bei der gilt:
;$b[Rest] <> 0 wobei Rest = mod ( Vielfaches der Prim , 30 )
;
;die Vielfachen der Primzahlen werden eliminiert, indem an ihre Position in der Matrix eine Zahl (zur Verdeutlichung das Vielfache) geschrieben wird
;Ist das Sieb fertiggestellt, sind die Arrayelemente mit 0 die Primzahlen, alle anderen sind eliminierte Vielfache
$tt = TimerInit()
[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]$a[1]=1
$flag = 0
$primstring = ""
For $x = 0 To $arraysize ;Anzahl aller möglichen Primzahlen in der Matrix
For $y = 0 To 7 ;jedes Element in der Zeile
If $a[$y + 1 + ($x * 8)]<>0 Then ContinueLoop ;nur Elemente mit 0 sind Primzahlen
$prim = $x * 30 + $spaltenindex[$y] ;das ist die Primzahl
$qprim = $prim ^ 2 ;alle Vielfachen ab dem Quadrat dieser Primzahl eliminieren...
If $qprim > $limit Then ExitLoop 2 ;wenn Quadrat der Primzahl > Wurzel aus limit, dann besteht das sieb nur noch aus Primzahlen
$r = Mod($qprim, 30) ;mod der Zahl liefert den Rest
$d = Int($qprim / 30) ;int/30 liefert die Zeile der Zahl
If $b[$r] <> 0 Then ;wenn Zahl ein Vielfaches eines der Spaltenindizes, dann alle weiteren Vielfachen eliminieren
$a[$b[$r] + ($d * 8)] = $prim ;Im Arraydisplay sieht man sehr schön die eliminierten Vielfachen
$t=timerinit()
$w=0
For $m = $qprim To $limit Step $prim ;alle Vielfachen aus der Matrix eliminieren
$r = Mod($m, 30)
$d = Int($m / 30)
If $b[$r] <> 0 Then
$a[$b[$r] + ($d * 8)] = $prim
EndIf
$w+=1 ;anzahl eliminierter Zahlen = Vielfache der Prim
Next
$m=timerdiff($t)
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $m = ' &$prim&" "&$w&" "& $m & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
endif
Next
Next
$m = TimerDiff($tt)
Msgbox(0,"Komprimiertes Sieb von Eratosthenes"," Primzahlen in "&int($m)&" Millisekunden!" & @CRLF &"Bitte im Anschluss kurz auf das Arraydisplay warten....")
_ArrayDisplay($a)
$primstring = "2" & @CRLF & "3" & @CRLF & "5" & @CRLF
$n = 3
For $i = 1 To $arraysize - 2
If $a[$i + 1] = 0 Then ;Primzahl im Sieb gefunden
$r = Mod($i, 
$d = Int($i /
$n += 1
$primstring &= $d * 30 + $spaltenindex[$r] & " " & $n & @CR ;Ausgabe der Primzahlen
EndIf
Next
ConsoleWrite($primstring)
Exit
Sieb von Atkin:
Spoiler anzeigen
;Sieb von Atkin
$limit=1299709;10^8
global $struct=dllstructcreate("byte["&$limit&"]")
$t=timerinit()
$q=int(sqrt($limit))
for $x=1 to $q
for $y=1 to $q
$n=4*$x*$x+$y*$y
if $n<$limit and (mod($n,12)=1 or mod($n,12)=5) Then _flip($n)
$n=3*$x*$x+$y*$y
if $n<$limit and (mod($n,12)=7) Then _flip($n)
$n=3*$x*$x-$y*$y
if $x>$y and $n<$limit and (mod($n,12)=11) Then _flip($n)
Next
Next
$a=2
For $i=5 to $limit step 2
if dllstructgetdata($struct,1,$i)=1 Then
$e=$i*$i
$a+=1
for $z=$e to $limit step $i
dllstructsetdata($struct,1,0,$z)
next
EndIf
next
$m=timerdiff($t)
Msgbox(0,"Sieb von Atkin","Zeit für die Primzahlen bis "&$limit & @CRLF & int($m) &" Millisekunden")
for $i=1 to $limit
if dllstructgetdata($struct,1,$i)=1 Then consolewrite ($i & @CRLF )
next
func _flip($z)
if dllstructgetdata($struct,1,$z)=1 Then
dllstructsetdata($struct,1,0,$z)
else
dllstructsetdata($struct,1,1,$z)
EndIf
endfunc
..oder überrascht mich^^