primzahlenrechner

Einmal das Consolewrite rausnehmen, aber vor allem:
Kein _ArrayDelete. Stattdessen einfach nen Wert wie -1 eintragen, der nie erreicht werden kann. Beim ArrayDelete wird im Hintergrund jedesmal ein neues Array erzeugt, mit den alten Daten beschrieben, und wieder zurückgegeben. Das dauert.
Wenn du -1 eingetragen hast: einfach nach der Größe sortieren und dann mit ReDim alle restlichen "abschneiden". Dabei wird dann nur 1x das Array neu erzeugt. Musst dann nur ne ausnahmeregel für -1 einbauen.

Naja... ob du jeden schleifendurchlauf _arraydelete nutzt, oder ob du einmal nach der schleife sortierst und dann redim nutzt macht eigentlich nen ziemlich großen unterschied^^.
Aber nen Index macht natürlich auch sinn

Hey ProgrammingDonkey!
Ich bin zu faul um mich hinter deinen Gedanken zu deinem Skript einzulesen, das eine oder andere Kommentar hätte sicherlich geholfen. Was mir jedoch konkret ins Auge springt ist das _ArrayDelete(). Bei jedem Aufruf wird das Array neu dimensioniert, das kostet viel Zeit. Um Optimierungen vorzunehmen muss man erst einmal genau wissen was man möchte. Bei dieser Primzahlen-Geschichte kann man bereits mathematische Gesetze ausnutzen. So wie ich das sehe tust du das nur bedingt, da kann man tatsächlich viel mehr rausholen als wie es den Anschein hat. Du hattest mich um eine Erklärung zu meinen Skript gebeten, um das allerdings zu verstehen muss der Gedanke dahinter verstanden werden. Ich versuche es mal zu erklären, eine Optimierung deines Codes kannst du anhand des gewonnenen Wissens dann selber vornehmen.

Mein Algorithmus tut eigentlich nur folgendes:
1. Es wird eine Liste angelegt von 2 bis N Elementen (in Form eines 1D Arrays)
2. Es wird die kleinste Zahl aus der Liste gesucht welche noch nicht „durchgestrichen“ ist, dies muss eine Primzahl sein.
3. Alle Vielfachen der Gefunden Zahl werden „durchgestrichen“.
4. Gehe wieder zu Schritt 2 und wiederhole die Schritte bis das Ende der Liste erreicht wurde.
5. Alle nicht durchgestrichenen Zahlen sind Primzahlen.

Anders gesagt arbeitet dieser nach dem Sieb des Eratosthenes. Eine einfache Implementierung würde folgendermaßen aussehen:

Wenn wir uns mal Zeile 4 anschauen, so sehen wir folgende Rechnung:Sqrt($limit). Es ist so, dass nur alle Zahlen bis zu der Quadratwurzel der Endzahl abgeklappert werden müssen. Bei 100 Primzahlen müssen also nur alle Vielfachen von 2 bis 10 tatsächlich durchgestrichen werden. Alle anderen Zahlen zu überprüfen und deren Vielfache durchzustreichen wäre lediglich nur Zeitverschwendung. Dies liegt daran dass wir jede Zahl in ihre Primfaktoren zerlegen können. Das bedeutet, dass die Zahl eine Vielfache des Primfaktor ist. Und maximal 1 Primfaktor (und das muss nicht mal unbedingt so sein) kann größer sein als die Quadratwurzel jener Zahl. Alle anderen Primfaktoren liegen damit unter der Quadratwurzel. Ein Beispiel wird dies nochmal verdeutlichen:

Nehmen wir an wir wollen alle Primzahlen bis 1000 ermitteln. Die Quadratwurzel dieser Zahl ist 31,62. Wenn wir die Zahl 1000 in ihre Primfaktoren zerlegen erhalten wir die Faktoren 2^3 * 2^5. Das bedeutet dass 1000 die Vielfache von 2 und 5 ist. Nun zerlegen wir die 999: 3^3 * 37 Wir sehen dass ein Faktor über der Quadratwurzel von 31,62 liegt. Ist aber soweit nicht tragisch da der Faktor 3 noch darunter liegt. Streichen wir also alle Vielfachen von 3 weg, so ist auch die 999 durchgestrichen. Dies kann man jetzt für jede Zahl fortführen, das System geht auf. Deshalb brauchen wir nur alle Zahlen von 2 bis Sqrt(n) durchlaufen da sowieso alle Vielfachen weggestrichen werden. Ich hoffe es ist so verständlich.

Schauen wir uns jetzt noch Zeile 17 an: For $m = $n ^ 2 To $limit Step 2 * $n
Wir starten bei $n ^ 2. Warum ist das allerdings so? Potenzieren wir unsere Startzahl (meinetwegen die 3) so stellen wir fest dass die 6 dabei übersprungen wird. Durch das Step 2 * $n werden auch die 12, 18 und 24 übersprungen. Bei der 5 wären dies die Zahlen 10, 15, 20, 30, 40 usw. Wir sehen also, dass (beinahe) nur gerade Zahlen übersprungen werden, die Schleifendurchläufe werden weniger und so brauchen wir weniger Zeit. Was ist aber nun mit der 15? Nun ja, die 15 wird durch die 3 (da diese dort nicht übersprungen wird) durchgestrichen, dies verhält sich bei allen Zahlen so. Die kleineren Zahlen streichen jene Zahlen durch, welche die größeren überspringen. Zeit wird so aber definitiv eingespart.

Nun ist der Algorithmus aber noch nicht perfekt da es noch sehr lange dauert bis alle Primzahlen ermittelt wurden. Bei 1'000'000 als Limit braucht dieses Verfahren ca. 9 Sekunden bei mir. Da geht aber noch mehr.

Eine weitere Erklärung zu dem Rest folgt noch
Gerade keine Lust mehr zu tippen

Bevor ich es vergesse, hier mal eine andere Version des Algo in Beitrag #18.
Könnt ihr mal eure Ergebnisse posten? Bei mir braucht das mit den String Funktionen etwas unter einer Sekunde.

@Make-Grafik >> Mein Script macht genau das gleiche, nur das die Zahlen Liste nur aus ungeraden besteht. Erklärende Kommentare bräuchte dein Script btw auch ^^.
An die anderen >> Danke für die schnelle Hilfe, ich versuche es gleich auch ohne _ArrayDelete in der Schleife.
@Kanashius >> Das ConsoleWrite() macht zeittechnisch keinen Unterschied (habe ich getestet), deshalb habe ich es zur Darstellung drin gelassen

Neues Script:

Stimmen die Primzahlen? Sind es 333334 bis eine Mio?

1-20 = 8 Primzahlen, und die stimmen auch noch alle

EDIT: Aber bei 30 schleicht sich die 25 ein. Mal sehen

Das Problem liegt an der Abbruchbedingung. Siehe kommentierte Zeile:

Okey, bei dir entspricht Zeile 25 meiner auskommentierten Zeile. Habe das Skript nur mal auf das nötigste komprimiert. Wie du siehst wird das Array abgeklappert bis wir auf -1 bzw. False treffen. Wenn wir das Skript bis 30 durchlaufen lassen, passiert folgendes:

Alles ungeraden Zahlen ab 3 bis 30 aufschreiben:
3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

Nun überprüfen welche der Zahlen eine Vielfache von der aktuellen Primzahl ist, bei 3 fangen wir an:

3 <> 5
3 <> 7
3 = 9 >> 9 wird ausradiert
usw...

Folgende Liste bleibt über:
3, 5, 7, -, 11, 13, -, 17, 19, -, 23, 25, -, 29

Gleiches Spiel, dieses mal mit der 5:
5 <> 7
5 <> - >> Abbruchbedingung erfüllt.

Nun geht’s mit der 7 weiter:
7 <> - >> Abruchbedingung erfüllt

Du siehst wo das Problem ist? Ich weiß was du damit bezwecken willst, habe auch schon die Lösung. Die Abbruchbedingung gehört nicht in die zweite For-Schleife sondern muss abgefragt werden BEVOR diese überhaupt gestartet wird:

Wie du siehst wird jetzt auch die 25 degradiert.

Danke für die Hilfe, dieses Problem hatte ich allerdings schon beseitigt. Das ganze dauerte dann aber viel länger.. Morgen Nachmittag kann ich deine Verbesserung testen, ich hoffe, dass mein neues Problem dort nicht auftritt

Nein - leider dauert das ganze wieder viel länger