Hallo, ich soll ein Programm schrieben, das in einer vorgegebenen Zeit (10 Minuten) möglichst viele Primzahlen suchen kann. meine einzigste Vorgabe sind die 10 Minuten, und das das ganze mit einem Algorithmus geschehen soll. Nun habe ich mir bereits das Sieb des Eratosthenes angesehen, aber damit kann ich nicht direkt die vorgegebene zeit einhalten, da ich erstmal die zahlen auflisten muss. und einige Rechner ja schneller laufen als andere. Gibt es irgendwie etwas, mildem ich auf die Zeit aufbauen kann? und Wäre es ein Algorithmus wenn ich einfach alle zahlen durchprobiere und prüfe ob es eine Primzahl ist?
Moin,
vorgegebenen Zeit (10 Minuten) möglichst viele Primzahlen
suchen kann. meine einzigste Vorgabe sind die 10 Minuten, und
das das ganze mit einem Algorithmus geschehen soll. Nun habe
ich mir bereits das Sieb des Eratosthenes angesehen, aber
Jedes Computerprogramm ist qua Definitionem ein Algorithmus, auch ein Monte-Carlo-Ansatz, der im Wesentlichen eine schöne Bezeichnung für Würfeln ist. Gezieltes Ausprobieren ebenso.
Beim Sieb des Eratosthenes könntest Du einfach eine schöne große Menge an Zahlen Dir vorgeben und schauen wie weit Du kommst. Anhand Deines eigenen Rechners kannst Du ja abschätzen wie viel in gegebener Zeit auszurechnen geht und einfach eine 10-fach Reserve oder so einplanen. Speicher belegen ist schnell, das Rechnen nur dauert länger…
Ansonsten: ein wenig auf Wiki und ihren verlinkten Seiten herumstöbern führt zu diesem Link:
http://cr.yp.to/primetests.html
Gruß,
Ingo
Tach,
vielleicht hilft dir das weiter http://de.wikipedia.org/wiki/Sieb_von_Atkin
okay danke schonmal… gibt es denn irgendein mathematischen beweis, ob eine zahl eine Primzahl ist? sowas wie ne formal, wo man seine Zahl einsetzt, und wenn das und das rauskommt ist es eine Primzahl
sry, wenn die Frage dumm klingt, aber ich bin nciht so beflügelt in Mathematik^^
Es gibt keine einzelne Formel, die Dir alle Primzahlen ausspuckt oder die ja/nein sagt, ob eine natürliche Zahl n prim ist oder nicht; deshalb sind ja die Primzahlalgorithmen so interessant, sie alle sind mehr oder minder eine mögliche Lösunge Deiner Aufgabe (sonst wäre Deine Aufgabe auch fast witzlos), haben aber alle verschiedene Vor- und Nachteile.
Die von mir verlinkte Seite gibt im übrigen einen scheinbar[1] großen Überblick über die verfügbaren Algorithmen und gibt auch Laufzeitabschätzungen für a) das Auffinden eines möglichen Primzahlkandidaten und b) das Überprüfen auf Primzahleigenschaft für jeden einzelnen Algorithmus, soweit bekannt. Das heißt nicht, dass die neuesten Algorithmen einfach zugänglich wären, da steckt jede Menge Zahlentheorie dahinter.
So wie Du fragst, dürfte Euch eine Implementation von Eratosthenes oder Atkins (wie Anja empfiehlt) Algorithmen sinnvoll erscheinen. Wer Spaß an Mathe hat, zieht sich ein paar der anderen Algorithmen rein 
Gruß,
Ingo
ok danke, ich hatte eigentlich nur gefragt weil wir in Mathe hatten, das n^2+1 immer eine Primzahl ist, und ob man die Formel nicht umkehren könnte so Wenn die Wurzel aus n minus eins eine Ganzzahl ist, ist n eine Primzahl . aber da kommt bei mir ziemlicher kappes raus 
Hey Axel,
das n^2+1 immer eine Primzahl ist
das hört aber ganz schnell auf, dass diese „Formel“ richtig ist
n=1: 2 passt
n=2: 5 passt
n=3: 10 hmm
n=4: 17 passt
n=5: 26 hmm
Bei den ersten 5 natürlichen Zahlen 2 Fehltritte - ist sicherlich kein guter Anfang für eine Formel 
Gruß René
Hallo,
ist sicherlich kein guter Anfang für eine Formel
(lach) Eine mögliche andere Erklärung wäre, dass der Fragesteller eigentlich
2^{2^n} + 1
(n ≥ 0) meinte. Das sind die Fermatzahlen. Pierre de Fermat glaubte, dass alle Zahlen dieser Form Primzahlen sind. Sein Traum zerrann nach seinem Tod, als Euler eine Zerlegung der sechsten Fermatzahl fand. Heute vermutet man, dass außer den ersten fünf Fermatzahlen keine weiteren prim sind.
Gruß
Martin
Hey Martin,
ahh, davon hab ich schon mal gehört Hätte ich aber auch drauf schliessen können - danke.
Wo wir schon bei den Fermatzahlen sind, kannst du mir evtl auch eine Frage beantworten, die mich interessiert:
Ich habe gelesen („Mathematik für Sonntagmorgen“ von Szpiro), dass von den ersten 2.500.000 Fermatzahlen erst 217 überprüft wurden. Dass die Überprüfung einer Zahl lange dauert ist mir durchaus bewusst, aber ich habe noch nicht den Sinn dahinter verstanden, z.B. die Zerlegung der 2.478.782-ten Fermatzahl zu zeigen, wenn ich noch nicht mal die ersten 300 vollständig gezeigt habe.
Warum geht man da nicht der Reihe nach vor bzw. wie kommen die auf die verschiedenen Zahlen zur Überprüfung?
Eine Erklärung, die mir einfallen würde, wäre, dass sie Produkte beliebiger Primzahlen mit den Fermatzahlen vergleichen. Wenn sie eine Übereinstimmung haben, war die Fermatzahl keine Primzahl.
Dann versteh ich allerdings nicht, warum die ersten Fermatzahlen nicht schon längst überprüft wurden
Gruß René
Hallo,
in vielen Programmiersprachen kann man (mit mehr oder weniger viel Aufwand) Timer einsetzen, die den Prozess nach einer bestimmten Zeit abbrechen.
Ansonsten ist ein sehr simpler, aber dafür auch nicht arg effizienter Ansatz der folgende:
Für n > 1 aus den natürlichen Zahlen wird geprüft, ob n mod k = 0 ist, wobei k von 2 bis Wurzel(n)+1 läuft. Für n mod k = 0 gehst Du zum nächsten n, sonst (also wenn bis Wurzel(n)+1 nicht abgebrochen wurde), gibst Du die Zahl aus, sie ist dann eine Primzahl.
Grüße,
d.
okay danke schonmal… gibt es denn irgendein mathematischen
beweis, ob eine zahl eine Primzahl ist? sowas wie ne formal,
wo man seine Zahl einsetzt, und wenn das und das rauskommt ist
es eine Primzahl
Hallo,
nach dem Satz von Wilson ist eine Zahl p genau dann prim wenn
(p-1)!≡p-1 mod p
http://de.wikipedia.org/wiki/Satz_von_Wilson
Sowas lässt sich relativ einfach implementieren, hab ich mal gemacht, das sind ein paar Zeilen code. Wichtig dabei ist, dass du immer wieder modulo p rechnest damit die Zahlen klein bleiben. Bei Fragen kannst du dich ja nochmal melden.
Gruß
hendrik
1 „Gefällt mir“
Hi,
Eine Antwort, die mir dazu einfallen würde, ist, dass kleine Primzahlen nicht so „interessant“ sind wie große/lange.
Große Primzahlen werden heutzutage für die meisten Verschlüsselungen benötigt, allerdings müssen die wirklich lang sein, damit man die Verschlüsselung nicht durch erraten knacken kann.
Es hat also von der Anwendung her nicht so viel Sinn die kleinen zu Überprüfen, da man sie hinterher sowieso nicht verwenden kann.
Gruß
Merlin
Hey Merlin,
der Gedanke ist durchaus richtig, aber ich würde die Fermatzahlen nicht als kleine Zahlen abstempeln Bei den meisten Verschlüsselungsmethoden werden Zahlen von mehren hundert Ziffern verwendet werden.
Dies ist aber spätestens schon bei 2^{2^{20}}+1 der Fall.
2^{2^{2478782}}+1 dann als nächste Zahl zu untersuchen, finde ich dann schon bissl übertrieben
Gruß René
PS:
damit man die Verschlüsselung nicht durch erraten knacken kann.
Bei mir hätte es schon bei der Größenordnung der 5-ten Fermatzahl mit dem Erraten nicht mehr geklappt Aber ich glaub die Zeiten der Raterei sind vorbei
Hallo TheBozz,
Ich habe gelesen („Mathematik für Sonntagmorgen“ von Szpiro),
dass von den ersten 2.500.000 Fermatzahlen erst 217 überprüft
wurden. Dass die Überprüfung einer Zahl lange dauert ist mir
durchaus bewusst, aber ich habe noch nicht den Sinn dahinter
verstanden, z.B. die Zerlegung der 2.478.782-ten Fermatzahl zu
zeigen, wenn ich noch nicht mal die ersten 300 vollständig
gezeigt habe.
Warum geht man da nicht der Reihe nach vor bzw. wie kommen die
auf die verschiedenen Zahlen zur Überprüfung?
das hat einen simplen Grund: Die Verfahren, die überhaupt eine Chance bieten, irgendwelche Teiler solch gigantischer Zahlen (deren Größe außerhalb jeder menschlichen Vorstellungskraft liegt) zu finden, haben mit manchen Zahlen aus bestimmten, diffizilen Gründen leichteres Spiel als mit anderen. Einige der sehr großen Fermatzahlen sind einfach more easy als andere viel kleinere.
Alle „trivialen“ Algorithmen (Probedivision, Sieb des Eratosthenes u. ä.) sind mit der Aufgabe der Faktorisierung so großer Zahlen hoffnungslos überfordert – egal wieviel Prozessoren mit wieviel Gigahertz und wieviel Gigabytes RAM der Rechner hat. Das können nur höchstspezialisierte Algorithmen leisten, die auf bestimmten zahlentheoretischen Zusammenhängen basieren und niveaumäßig ungefähr ein paar Lichtjahre jenseits von Schulmathematik angesiedelt ist. Und selbst die haben nur bei wenigen „leichten“ Zahlen Erfolg. Ein Verfahren, das alle großen Zahlen schnell faktorisieren kann, gibt es ja bekanntlich nicht.
Erklärung, die mir einfallen würde, wäre, dass sie Produkte
beliebiger Primzahlen mit den Fermatzahlen vergleichen.
Jeden naiven Ansatz dieser oder ähnlicher Art kannst Du völlig vergessen. Da würdest Du rechnen, bis die Sonne kalt geworden ist – ich meine es wörtlich
Gruß
Martin
Hallo,
Nun habe ich mir bereits das Sieb des Eratosthenes angesehen, aber
damit kann ich nicht direkt die vorgegebene zeit einhalten, da
ich erstmal die zahlen auflisten muss. und einige Rechner ja
schneller laufen als andere.
ja, das hast Du richtig erkannt. Es gibt aber eine Lösung: Du misst einfach die Geschwindigkeit des Rechners. Dazu machst Du zunächst einen Vortest, indem Du das SdE mit ein paar verschiedenen Limits n laufen lässt und schaust, welche Laufzeit-von-Limit-Funktion t(n) Deine Implementierung hat. Diese Funktion hat die Form t(n) = C nE. In dem Vortest ausmessen musst Du den Exponent E, der von Deinem Algorithmus abhängt. In der Konstanten C dagegen ist die Leistungsfähigkeit des PCs berücksichtigt.
Dein Programm legst Du dann so aus, dass Du das SdE zweimal laufen lässt. Zuerst mit einem so kleinen Limit, dass es nach ein paar Sekunden fertig ist. Die Laufzeit misst Du und bestimmst daraus den Wert von C für diesen Rechner und daraus wiederum dasjenige Limit, das die 10 Minuten voraussichtlich ausschöpfen wird. Danach startest Du das SdE mit diesem Limit.
Das zu realisieren ist nicht so wild wie es sich anhören mag, und es lohnt die Mühe, weil das SdE schneller ist als Probedividieren (und Dein Lehrer ist davon sicher auch beeindruckt). Es setzt allerdings eine gigantische Menge RAM voraus. Wenn Du die Möglichkeit hast, z. B. 1 GByte Speicher als RAM zu allokieren (z. B. hat Delphi mit der Deklaration „a: ARRAY[0…999999999] OF BYTE“ nicht das geringste Problem), rate ich Dir zum SdE. Der Rechner muss aber auch soviel physischen RAM haben. Nicht weniger, sonst wird auf die Festplatte ausgelagert, und das ist schnarchlahm.
Wäre es ein Algorithmus wenn ich einfach alle zahlen durchprobiere
und prüfe ob es eine Primzahl ist?
Ja, und wenn Du nur wenig Speicher auf dem Rechner allokieren kannst oder darfst, bleibt Dir sogar nicht viel anderes übrig.
Gruß
Martin