[Contest] Primzahlen Contest

[Lawliet]

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.

['Henry.]

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

[Lawliet]

Wie du willst. Aber nach dem messen der zeit müssen sie irgendwie ausgegeben werden.
Und ja, es kommt nur auf die Zeit an.

['Henry.]

gibts n Code stück, womit man die Zeit seines Algos prüfen kann oder muss ich mir das selber schreiben^^

[Requi]

Interessant, lasse mir mal was einfallen

[Lawliet]

Habe mal die Anforderungen um diesen Satz erweitert:

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.

[lolkop]

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:

#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.

['Henry.]

-.- wollts auch mit dem Sieb des Eratosthenes lösen^^ ist bis 10^10 effizient nur mal so zur information

[lolkop]

Originally Posted by henry0692

-.- wollts auch mit dem Sieb des Eratosthenes lösen^^ ist bis 10^10 effizient nur mal so zur information

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...

 Spoiler

$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 =)

['Henry.]

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^^

[lolkop]

Originally Posted by henry0692

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.

[Lawliet]

Schonmal jemand das sieb von atkin implementiert?

[lolkop]

Originally Posted by Lawliet!

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...

[Lawliet]

Hm, ok hatte mir den noch garnicht so genau angeschaut.

[butter123]

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:

 Spoiler

PHP Code:

#include <array.au3>
$z =  TimerInit()
getPrimesTo(100000)
$x = TimerDiff($z)
ClipPut($x)


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.

edit 2: 4. hinzugefügt