Hallo Leute,
ich dachte ich mach hier mal einen kleinen Primzahlen Contest.
Es geht darum in Au3 einen Algo zu erstellen, der möglichst schnell alle Primzahlen zwischen 0 und 100000 ermittelt.
Es sind nur die standardmäßigen Funktionen erlaubt!
DllCall, UDFs usw. sind also nicht erlaubt.
Am Ende müsst ihr eine Funktion mit einem Parameter haben, in die 100000 übergeben wird. Geprüft wird per TimerInit() und TimerDiff() nach dem Aufruf der Funktion.
Die fertigen Scripte dann bitte hier posten, damit ich sie auf meinem Rechner unter gleichen bedingungen testen kann
Als Preis gibt es 10 e*Gold.
Ende ist am 14.03.2013
lg
Falls ihr eine Idee und einen Preis für einen anderen Contest habt, meldet euch bei mir
Ihr bekommt dann dafür auch über einen Zeitraum einen sticked Thread.
Es kommt also nur auf Schnelligkeit an, Script darf also unbegrenzt groß sein?
Sollen die Primzahlen am Ende in einem Array oder Liste stehen? Sollen diese nur in der Konsole ausgegeben werden?
Habe mal die Anforderungen um diesen Satz erweitert:
Quote:
Am Ende müsst ihr eine Funktion mit einem Parameter haben, in die 100000 übergeben wird. Geprüft wird per TimerInit() und TimerDiff() nach dem Aufruf der Funktion.
meines wissens nach ist doch das immernoch die effizienteste methode primzahlen in einem gewissen intervall zu ermitteln...
umsetzen kann man das ganze relativ simpel so:
Code:
#include <array.au3>
$p = getPrimesTo(100000)
_ArrayDisplay($p)
Func getPrimesTo($limit)
Local $t[$limit+1], $p[$limit+1] = [0]
For $a = 2 To $limit
If $t[$a] <> 1 Then
If $a <= Sqrt($limit) Then
For $b = 2*$a To $limit Step $a
$t[$b] = 1
Next
EndIf
$p[0]+=1
$p[$p[0]]=$a
EndIf
Next
ReDim $p[$p[0]+1]
Return $p
EndFunc
Edit:
zurückgegeben wird ein array, in welchem der index 0 die anzahl der primzahlen enthält... die restlichen einträge sind die primzahlen selbst.
$t = TimerInit()
$p = getPrimesTo(100000)
ConsoleWrite(TimerDiff($t)&@CRLF)
Func getPrimesTo($limit)
Local $t[$limit+1], $p[Ceiling($limit/2)+1] = [1,2]
For $a = 3 To $limit Step 2
If $t[$a] <> 1 Then
If $a <= Sqrt($limit) Then
For $b = 2*$a To $limit Step $a
$t[$b] = 1
Next
EndIf
$p[0]+=1
$p[$p[0]]=$a
EndIf
Next
ReDim $p[$p[0]+1]
Return $p
EndFunc
nimmt man beispielsweise, wie oben gezeigt, die 2 bereits von anfang an ins array und überspringt somit alle geraden zahlen von anfang an, spart man sich ca 1/3 der laufzeit... allerdings wäre damit der algorithmus in gewissem sinne vorgetäuscht...
spielt man das ganze so weiter, könnte man am ende theoretisch auch die zahlen bis an die zahlengrenze von autoit vorgeben und je nach input wert, einfach das fertige array abschneiden und ausgeben in unter 1ms....
letztendlich ist der erste von mir gepostete weg oben aber der eigentlich korrekte =)
gut lolkop, ich gebe auf^^ genauso wollte ich es auch machen und ne verbesserung fällt mir jetzt auch nicht ein, eventuell könnteste dir die Anzahl sparen, dann wirds noch schneller^^
gut lolkop, ich gebe auf^^ genauso wollte ich es auch machen und ne verbesserung fällt mir jetzt auch nicht ein, eventuell könnteste dir die Anzahl sparen, dann wirds noch schneller^^
will man ein array nur mit primzahlen ausgeben, muss man ohnehin immer einen counter laufen lassen... ob dieser nun im eigenen array auf dem index 0 mitläuft, oder in einer seperaten variable, macht am ende keinen unterschied.
da du bei atkin eine erhöhte vorarbeit leisten musst, ist es in der vom wettbewerb festgelegten dimension definitiv nicht so effizient wie der vorgestellte algorithmus...
das problem was ich bei wettbewerben zu so bekannten verfahren sehe ist, dass man das als wissenschaftlich am schnellsten annerkannte verfahren implementiert und fertig. und das alle das skript benutzen und es noch irgendwie tweaken.
ich konnte lolkops skript um ca 20 ms verbessern^^
1. sqrt($limit) vorher angeben und nicht bei jedem durchlauf neu berechnen
2. beim streichen der zahlen nicht bei 2*$a anfangen sondern bei $a*$a
3. $p nicht mit 0 füllen (glaube macht kein unterschied, passiert sowieso)
4. erste If abfrage durch switch ersetzt. bei der 2. konnte ich kein zeitunterschied erkennen.
Func getPrimesTo($limit) Local $t[$limit+1], $p[$limit+1] Local $c = Sqrt($limit) For $a = 2 To $limit Switch $t[$a] case 0 If $a <= $c Then For $b = $a*$a To $limit Step $a $t[$b] = 1 Next EndIf $p[0]+=1 $p[$p[0]]=$a EndSwitch Next ReDim $p[$p[0]+1] Return $p EndFunc
edit: zu atkin: soweit ich das bei wiki verstanden habe setzt man vorraus, dass man weiß, 2,3,5 sind prim. wäre ja auch eig geschummelt sonst könnte man bei lolkop glaub ich auch alle geraden durch ein step 2 rausschmeißen.
![[Contest] Primzahlen Contest](https://www.elitepvpers.com/forum/iconimages/autoit/contest-primzahlen-contest_ltr.gif){kind=small}
immernoch die effizienteste methode primzahlen in einem gewissen intervall zu ermitteln...
sonst könnte man bei lolkop glaub ich auch alle geraden durch ein step 2 rausschmeißen.
