Sieb des Eratosthenes

TheLuBu

Hallo liebe Community,
Ich habe mich ein bisschen durch http://rosettacode.org gewühlt und bin auf das Sieb des Eratosthenes gestoßen.

Ich habe mir meine Gedanken dazu gemacht und den folgenden Code auch schon eingefügt:

Spoiler anzeigen

[autoit]

#include <Array.au3>
$Input = InputBox("Integer", "Enter biggest Integer")
$timer = TimerInit()
Global $array[$Input][2], $retarray[1], $counter = 0, $txt = ""
For $i = 2 To UBound($array)
$array[$i - 1][0] = $i
$array[$i - 1][1] = -1
Next
For $i = 1 To UBound($array) - 1
If $array[$i][1] = -1 Then
$array[$i][1] = 1
_ArrayAdd($retarray, $array[$i][0])
$counter += 1
For $k = $i To UBound($array) - 1 Step $array[$i][0]
$array[$k][1] = 0
Next
EndIf
Next
$retarray[0] = $counter
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : TimerDiff($Timer) = ' & TimerDiff($Timer) & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
_ArrayDisplay($retarray)

[/autoit]

Ich würde jetzt gerne von euch wissen, ob man das noch irgendwie schneller machen könnte.
Ich würde gerne das Ausgabeformat (Array mit den Primzahlen und Anzahl der Primzahlen in $array[0]) beibehalten, ich weiß das es mit einem String schneller gehen würde (ohne das _ArrayAdd). Ich komme jetzt bei Input = 1000 auf ~ 25ms, würde aber gerne wissen, ob es noch schneller geht

K4z

Ich denk das _ArrayAdd ist der größte Zeitfresser. Deutlich schneller ist das Array vorher zu groß anzulegen und am Schluss den Rest weg zuschneiden.
Frisst bei größeren Zahlen aber deutlich mehr Speicher. Ich hab einfach mal den Pseudocode von Wikipedia übersetzt, ist vielleicht auch noch nicht optimal aber deutlich schneller. Du kannst ihn dir ja einfach mal anschaun.

Spoiler anzeigen

[autoit]

#include <Array.au3>
$iMaxInteger = InputBox("Integer", "Enter biggest Integer")
$timer = TimerInit()
Dim $aStroked[$iMaxInteger], $aReturn[$iMaxInteger], $iCounter = 1
For $iI = 2 To $iMaxInteger-1
If Not $aStroked[$iI] Then
$aReturn[$iCounter] = $iI
$iCounter +=1
For $iJ = $iI*$iI To $iMaxInteger-1 Step $iI
$aStroked[$iJ] = True
Next
EndIf
Next
$aReturn[0] = $iCounter-1
ReDim $aReturn[$iCounter]
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : TimerDiff($Timer) = ' & TimerDiff($Timer) & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
_ArrayDisplay($aReturn)

[/autoit]

Edit: Ich brauch damit für 100000 ca. 360ms

**AspirinJunkie**

K4z hat es denke ich schon richtig erkannt.
Was wirklich Zeit frisst ist das ArrayAdd da dabei das komplette Array in einen größeren Speicherbereich neu geschrieben wird.
Das dauert natürlich umso länger je größer das Array ist.
Eine Möglichkeit wäre es daher auf dynamischere Speicherstrukturen wie z.B. das Scripting.Dictionary oder einen String auszuweichen statt einem Array auszuweichen.
Alternativ bleibt man bei einem Array und arbeitet nur mit Markierungen.

Nur zur Vollständigkeit, auch wenn es algorithmisch nicht anders ist als K4z's Lösung dass was ich gerade zusammengeschrieben habe:

Spoiler anzeigen

[autoit]

#include <Array.au3>
Global Const $d_Max = Int(InputBox("Integer", "Enter biggest Integer"))

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

; Array aller Zahlen erstellen:
Global $a_Numbers[$d_Max - 1][2]
For $i = 2 To $d_Max
$a_Numbers[$i - 2][0] = $i
$a_Numbers[$i - 2][1] = True
Next

[/autoit] [autoit][/autoit] [autoit]

; Algorithmus durchführen
For $i = 2 To $d_Max
If $a_Numbers[$i - 2][1] Then
For $y = $i * 2 To $d_Max Step $i
$a_Numbers[$y - 2][1] = False
Next
EndIf
Next

[/autoit] [autoit][/autoit] [autoit]

; Primzahlen ausgeben:
$s_Ret = ""
For $i = 0 To UBound($a_Numbers) - 1
If $a_Numbers[$i][1] Then $s_Ret &= $a_Numbers[$i][0] & ","
Next
$a_Primzahlen = StringSplit(StringTrimRight($s_Ret, 1), ",", 2)

[/autoit] [autoit][/autoit] [autoit]

_ArrayDisplay($a_Primzahlen)

[/autoit]

**Xenobiologist**

Hmmh, genau die gleiche Idee hatte ich auch. Ein bisschen was wird es sicher noch bringen, wenn du deine Varaiblennamen kürzt. (1 Zeichen)

K4z

Ich hab jetzt mal sämtliche Varianten ausprobiert (String, Active Directroy, Dllstruct) und irgendwie ist meine Variante immernoch am schnellsten. Was man noch machen kann, ist einfach alle geraden Zahlen auszulassen. Das bringt bei 1000000 immerhin eine Sekunde.

Spoiler anzeigen

[autoit]

#include <Array.au3>

[/autoit] [autoit][/autoit] [autoit]

$iMaxInteger = InputBox("Integer", "Enter biggest Integer")
$timer = TimerInit()
Dim $aStroked[$iMaxInteger], $aReturn[$iMaxInteger/2] = [0, 2], $iCounter = 2
For $iI = 3 To $iMaxInteger-1 Step 2
If Not $aStroked[$iI] Then
$aReturn[$iCounter] = $iI
$iCounter +=1
For $iJ = $iI*$iI To $iMaxInteger-1 Step $iI
$aStroked[$iJ] = True
Next
EndIf
Next
$aReturn[0] = $iCounter-1
ReDim $aReturn[$iCounter]
ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : TimerDiff($Timer) = ' & TimerDiff($Timer) & @crlf & '>Error code: ' & @error & @crlf) ;### Debug Console
_ArrayDisplay($aReturn)

[/autoit]

TheLuBu

Durch die Vorgabe der Aufgabe ist das Auslassen von geraden Zahlen nicht erlaubt

Zitat

That means especially that you shouldn't optimize by using pre-computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes.

Ich werde auch noch ein bisschen weiter testen, danke schonmal für die Anregungen

**Schnitzel**

Eigentlich wollte ich nur schnell was im Forum nachkucken aber auf diesen Thread muss ich dann doch antworten
Wir hatten mal nen Primzahlenwettbewerb:
https://autoit.de/index.php?page=Thread&threadID=18192