Primzahltest |
22.07.2007, 01:28 | matze(2) | Auf diesen Beitrag antworten » | ||
Primzahltest ich habe mir folgenden Primzahltest überlegt: Es sei die zu testende ungerade natürliche Zahl > 1, also Wenn für ein rational ist, so ist zusammengesetzt, andernfalls ist prim. Mich würde es nun freuen zu erfahren, ob dieses Verfahren noch optimierbar ist oder ob man es noch etwas verändern muss, damit es zu einer Wahrscheinlichkeit von ungerundeten 100% ein wahrheitsgemäßes Ergebnis liefert. |
||||
22.07.2007, 09:32 | Gast1234 | Auf diesen Beitrag antworten » | ||
Sei . Für ist |
||||
22.07.2007, 09:56 | Dual Space | Auf diesen Beitrag antworten » | ||
Stimmt, aber laut Voraussetzung soll in diesem Falle sein. |
||||
22.07.2007, 10:31 | AD | Auf diesen Beitrag antworten » | ||
@matze(2) Erstmal die gute Nachricht: Die Aussage stimmt. Jetzt aber die schlechte: Über Optimierbarkeit dieses Verfahrens zu sprechen macht m.E. wenig Sinn - denn der erkennbare Aufwand ist für einen Primzahltest miserabel. Selbst die übliche primitive Methode, alle ungeraden Zahlen kleiner oder gleich der Wurzel als Teiler zu überprüfen, schneidet mit Aufwand deutlich besser ab. |
||||
22.07.2007, 17:29 | matze(2) | Auf diesen Beitrag antworten » | ||
Das habe ich schon befürchtet. Ursprüglich wollte ich ein Verfahren finden mit dem man Primzahlen konstruieren kann, aber das ist sehr schwer. |
||||
22.07.2007, 18:23 | Dual Space | Auf diesen Beitrag antworten » | ||
So schwer nun auch wieder nicht: http://de.wikipedia.org/wiki/Primzahlen#..._von_Primzahlen Man muss das Rad ja nicht neu erfinden. |
||||
Anzeige | ||||
|
||||
22.07.2007, 19:15 | matze(2) | Auf diesen Beitrag antworten » | ||
"Es gibt allerdings Formeln, bei denen eine gewisse Wahrscheinlichkeit besteht, dass die erzeugten Zahlen eine Primzahl sein könnten. Trotzdem müssen die erzeugten Zahlen auf ihre Eigenschaft als Primzahl getestet werden." Ich würde eine Formel, die bei gegebenen Bedingungen allgemein gültig ist, viel schöner finden. |
||||
22.07.2007, 22:17 | Dual Space | Auf diesen Beitrag antworten » | ||
Vorsicht. Diese Aussage bezieht sich nur auf eine bestimmte Klasse von Formeln. Eben solche zur Berechnung der n-ten Primzahl. Du sprachst bisher nur von Formeln zur Berechnung von Primzahlen. Und da gibt es zahlreiche allgemein gültige Formeln. |
||||
24.07.2007, 02:25 | matze(2) | Auf diesen Beitrag antworten » | ||
Gut, ok, nun bin ich wieder einmal schlauer geworden Ja, so ist das heutzutage. Es gibt von dem, was man gebrauchen kann, schon fast alles und das, was es noch nicht gibt, wird es auch in unmittelbarer Zukunft noch nicht geben. (Jedenfalls in dem Niveau, bei dem ich mich noch befinde.) |
||||
24.07.2007, 08:37 | Dual Space | Auf diesen Beitrag antworten » | ||
Man muss bei der Forschung ja nicht immer gleich nach den Sternen greifen, sondern kann auch kleine Schritte machen. |
||||
25.07.2007, 20:52 | matze(2) | Auf diesen Beitrag antworten » | ||
Ja, das ist wirklich war. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |