Ich hab mom. 2 verschiedene Algos im Test und die benötigen etwa 6 bzw. 8 Sekunden.
die 3.3 Sekunden von Jonathan sind mir ein Rätsel, alleine eine For-Schleife von 0 bis 1299710 mit einer simplen If-Abfrage benötigt bei mir schon 2 Sekunden!
also 3,3 war bis jetzt auch mein absoluter spitzenwert... normalerweise so zwischen 3,7 und 4,5 Sek.
Edit:\\ oha mir ist ebend ein dicker fehler im script aufgefallen... son Fu** jetzt mus ich nochmal neu anfangen!! 
Mein Spitzenwert ist bis jetzt 336 Millisekunden für alle Zahlen bis 100 000.. Bis 1 000 000 sinds ca. 3 Sekunden 
Jetzt nochmal konkrete Fragen:
Soll ein Array zurückgegeben werden? Oder geschrieben werden?
Wird das Schreiben in die Zeitberechnung mit eingehen, oder nicht?
Edit: Und es soll alle Zahlen bis 100000 ausrechnen? Dann bitte im 1. Post korrigieren
Allgemein ist hier alles sehr verwirrend..
Edit2: Alle Primzahlen bis 1299710 berechnen (sind 100 000 zahlen).. geht das auch? Wenn ja, dann brauch ich bis dahin ca. 2,85 Sekunden (Durchschnitt aus 10 Messungen)
Dürfen die ersten Zahlen ohne Berechnungen als Primzahlen angenommen werden? 2, 3 vieeleicht noch 5?
Dürfen die ersten Zahlen ohne Berechnungen als Primzahlen angenommen werden? 2, 3 vieeleicht noch 5?
Wenn der Algorithmus darauf aufbaut, dass 2 und 3 Primzahlen sind, sind diese natürlich nicht berechenbar und sollten als gegeben betrachtet werden. Oder seht ihr das anders?
Oder seht ihr das anders?
ne, bin deiner Meinung... Wenn das zu dem AlgoRhytmus dazugehört, kann man das so machen^^
also jetzt habt Ihr mich auch angesteckt 
Aber mit den gegebenen Primzahlen als Rechenbasis, das sehe ich etwas skeptisch.
Da könnte ich ja die 5 und die 7 und die .... auch noch als gegebenen annehmen.
Ich finde ein Alghorythmus der Primzahlen erfasst, der sollte auch in der Lage sein eine 2 oder eine 3 zu erfassen.
Soll ein Array zurückgegeben werden? Oder geschrieben werden?
Wird das Schreiben in die Zeitberechnung mit eingehen, oder nicht?
Ich schlage vor, dass man das Ergebnis in beliebiger Form zurückgeben darf (String, Array, Datenbank, eine mit 7-Zip archivierte und mit AES verschlüsselte Textdatei, was auch immer). Hauptsache, es sind alle Primzahlen da, es gibt keine falschen Zahlen und die Zahlen sind voneinander getrennt.
Je nach Algorythmus ist die eine oder die andere Form vielleicht besser. Das Ergebnis anschließend zu konvertieren würde mehr Zeit kosten. Das ist imho unfair.
Das stelle ich mir dann so vor:
Timer wird initialisiert.
Die Funktion wird gestartet.
Timer wird gestoppt.
Die Zahlen werden aus Array / String / blablabla ausgelesen und in eine Textdatei geschrieben.
Die Textdatei wird auf Vollständigkeit und Fehler überprüft und die Zeiten werden verglichen.
Ich bin genau deiner Meinung.
Timer an
Funktion
Timer aus
In Datei schreiben
ich probiers auch mal aus 
Da könnte ich ja die 5 und die 7 und die .... auch noch als gegebenen annehmen.
Wenn du einen Algorithmus hast, der dadurch arbeitet, dass er genau das voraussetzt - warum nicht.
Allerdings ist mir grad kein Algo bekannt, der das tut. 2 und 3 - ja, aber 5, 7... etc. sind durch die Operationen mit 2 und 3 abgedeckt.
Lassen wir uns mal überraschen.
also ich finde, dass Euer Lösungsweg mit der For-Schleife bis 1299709 eigentlich Beschiss ist.
Ich ging davon aus, dass der Algorithmus in der Lage sein sollte selbst die letzte Primzahl zu errechnen.
Was ist das für eine Aufgabe, wenn ich sage:
Die 100000. Primzahl ist 1299709. Zähle bitte alle Primzahlen bis dahin auf.
Der Witz ist doch, das man eben nicht weiß welche Zahlen Primzahlen sind.
Ansonsten kann ich mir auch eine SQLite-DB mit den ersten 100000 Primzahlen erstellen und diese in ein Array einlesen.
Fertig.
Also mein Algorithmus beginnt mit der 3 als erste zu berechnende Primzahl und braucht für die Aufgabe 71 Sekunden
Ist jedoch universell einsetzbar für eine beliebige Anzahl zu suchender Primzahlen.
Man kann damit also auch die 100001 Primzahl finden.
Algo anbei Passwort geht an LEV.
also ich finde, dass Euer Lösungsweg mit der For-Schleife bis 1299709 eigentlich Beschiss ist.
Tja, genau da liegt aber der Hund begraben. Jeder schnelle Algoritmus benötigt irgendeine Obergrenze zum Rechnen. Wenn ich einfach nur fortlaufend rechne: _IsPrime(Zahl) - Next, so funktioniert das zwar, ist wie du selbst siehst aber schneckenlahm.
Und was ist Beschiss, wenn du weißt, dass bis 1299709 genau 100.000 Primzahlen vorkommen? Um Chancengleichheit zu wahren, habe ich ja diese Information gegeben.. :wacko:
Na ja, aber die "nächste größte Primzahl" kann man nach der Methode nicht errechnen.
Ich weiss, dass das nicht Gegenstand des µIT ist,
aber ich finde eine gewisse Nähe zur Realität (und die Diskussion begann ja auch über die größte Primzahl)
schon schön.
Na egal. Ich bin ja schon Stolz, dass ich es überhaupt geschafft habe ...
Na ja, aber die "nächste größte Primzahl" kann man nach der Methode nicht errechnen.
Nein, aber dafür braucht man dann eine Ausgangszahl. Die Funktion dafür ist bei mir "nebenbei" abgefallen :). _GetNearestPrime() ermittelt die nächsthöhere/ -kleinere Primzahl zur eingegebenen Zahl.
So, nach langer Zeit klinke ich mich mal wieder ein.
Hat sich ja einiges getan.
Erst mal alle Achtung! Das so viele mit so einem guten Algorithmus dabei sind...
Eigentlich ist es wirklich besser, die Grenze oben offen zu halten, halte mich aber mit Festlegungen zurück. Z.B. meine _MathEx_CreatePrimes()-Funktion ist (theoretisch) nach oben offen, dank Sieb des Eratostenes, oder wie der Freak da hieß.
Naja, allen viel Erfolg, das hier ist nichts offizielles.
Ich denke, ich sollte nochmal mit L3viathan2142 reden. Was meinst du dazu?
Schönes WE noch!
Matthias
Allerdings ist mir grad kein Algo bekannt, der das tut. 2 und 3 - ja, aber 5, 7... etc. sind durch die Operationen mit 2 und 3 abgedeckt.
Es geht. Durch die Definition kann man die Primzahlen bis 5 (also 3 und 5) ausrechnen. Wenn man alle geraden Zahlen und alle Vielfachen von 3 und 5 aus dem Zahlenpool eliminiert, und diese Zahlen in eine Liste packt, entsteht folgende Tabelle:
Alle Vielfachen von 2,3 und 5 eliminiert
Zahlen Spalte
1 2 3 4 5 6 7 8
Zeile
1 1 7 11 13 17 19 23 29
2 31 37 41 43 47 49 53 59
3 61 67 71 73 77 79 83 89
. Zahl=(Zeile-1)+30
es entsteht eine Tabelle, bei der man das Sieb des Eratosthenes anwenden kann.
Diese Tabelle kann man erstellen indem man ausschliesslich die Primzahlen bis incl 5 berücksichtigt!
Natürlich könnte man auch die Vielfachen von 7 und 11 eliminieren usw, allerdings stösst der Algorithmus hier an die Verwaltungsgrenzen...
Was muss man machen? Man ermittelt die Zahlen nacheinander und prüft per for/to bis sqrt(zahl) auf Prim. Manche löschen dann auch die Vielfachen dieser Zahlen (egal ob prim oder nicht) aus der Tabelle bzw ersetzen sie durch 1 (dann wird jede 1 in der Tabelle nicht weiter berücksichtigt.
/EDIT/ Man fängt bei der 2. Zahl( der 7) in der Tabelle an und löscht alle Vielfachen dieser Zahl aus der Tabelle, dann die 3. Zahl (die 11), alle Vielfachen löschen usw. solange, bis man die Zahl ereicht, die über der Hälfte der Obergrenze liegt. Dann sind alle Zahlen in der Tabelle bis zur Obergrenze Primzahlen.
Da der Inhalt einer "Zeile" 8 Zahlen sind, lassen sich diese in die 8 Bits eines Bytes(11111111) packen. So wurde das früher gemacht, um Speicherplatz zu sparen ^^. Dann muss man nur noch die Positionen der Vielfachen (Primen und nicht Primen ) an der Bitposition auf 0 setzen und man erhält ein komprimiertes Sieb...
Ich denke meine "Algorythmus" ist der einfachste/ineffizienteste, aber ich mache mal mit. 
Ich habe meine Versionen nun fertig!
Version 1 kommt ohne Obergrenze aus und man kann bestimmen, wieviele Primzahlen man haben möchte.
Laufzeit ca 60 Sekunden
Version 2 benötigt die besagte Obergrenze und liefert alle Primzahlen bis zu dieser.
Laufzeit ca 3,5 Sekunden (ist jedoch etwas unfair optimiert 
)
Und dann hab ich noch Version 3 mit etwa 700ms Laufzeit, fällt jedoch aus bestimmtem Grunde aus dem Wettbewerb raus 
Bei Version 1 verwende ich nicht MOD, sonderen etwas anderes
Dadurch ist sie um etwa 10 Sekunden schneller...
mfg
E
Hört sich alles sehr interessant an, ich bin schon gespannt auf alle Umsetzungen!
Ich ebenfalls wäre es der Jury vllt. möglich einen Ordner mit allen Lösungen zu erstellen, zu komprimieren und ihn irgendwo extern hochzuladen (wenn es dann so weit ist)
Denn ich hab schon ga keinen Überblick mehr wer eig. mitmacht 
mfg Ubuntu