Sieb des Eratosthenes

1. offizieller Beitrag

    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 :)

    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

    Zitat

    You just keep on trying 'till you run out of cake. ;)


    [STEAM] Source UDF

    Einmal editiert, zuletzt von K4z (4. September 2012 um 14:09)

    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]

    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]

    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

    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&amp;threadID=18192