[Contest] Primzahlen Contest

Page 1 of 2 1 2
03/07/2013 11:51 Lawliet#1
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.
03/07/2013 13:14 'Henry.#2
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?

mfg
03/07/2013 13:25 Lawliet#3
Wie du willst. Aber nach dem messen der zeit müssen sie irgendwie ausgegeben werden.
Und ja, es kommt nur auf die Zeit an.
03/07/2013 13:30 'Henry.#4
gibts n Code stück, womit man die Zeit seines Algos prüfen kann oder muss ich mir das selber schreiben^^
03/07/2013 13:33 Requi#5
Interessant, lasse mir mal was einfallen :D
03/07/2013 13:36 Lawliet#6
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.
03/07/2013 13:43 lolkop#7
meines wissens nach ist doch das [Only registered and activated users can see links. Click Here To Register...] 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.
03/07/2013 13:54 'Henry.#8
-.- wollts auch mit dem Sieb des Eratosthenes lösen^^ ist bis 10^10 effizient nur mal so zur information :D
03/07/2013 13:58 lolkop#9
Quote:
Originally Posted by henry0692 View Post
-.- wollts auch mit dem Sieb des Eratosthenes lösen^^ ist bis 10^10 effizient nur mal so zur information :D
auf meinem pc komme ich auf einen zeitwert von 300-400ms für die reine ausführung der funktion...

Edit:
theoretisch könnte man anfänge des arrays bereits vorgeben... weis aber nicht in wiefern das ganze gecheatet wäre...


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 =)
03/07/2013 14:09 'Henry.#10
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^^
03/07/2013 14:22 lolkop#11
Quote:
Originally Posted by henry0692 View Post
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.
03/07/2013 15:06 Lawliet#12
Schonmal jemand das sieb von atkin implementiert?
03/07/2013 15:33 lolkop#13
Quote:
Originally Posted by Lawliet! View Post
Schonmal jemand das sieb von atkin implementiert?
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...
03/07/2013 15:35 Lawliet#14
Hm, ok hatte mir den noch garnicht so genau angeschaut.
03/07/2013 15:42 butter123#15
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.

hier das skript:

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.

edit 2: 4. hinzugefügt
Page 1 of 2 1 2