Primzahl-Aufgabe
-
erstes gegenbeispiel (für Zahlen größer 5): 25 nicht prim, aber 25*25 % 24 =1.
-
Gibt es auch ein Gegenbeispiel, wo eine Primzahl nicht erkannt wird?
Wenn nicht, könnte man diesen Test als Vor-Test benutzen.
-
asmodis schrieb:
erstes gegenbeispiel (für Zahlen größer 5): 25 nicht prim, aber 25*25 % 24 =1.
Und wenn man Quadrate von Primzahlen ausschließt? Denn dieses Problem tritt auch bei 49 (7*7) und denke auch bei 121 (11*11) auf.
Also würde der Test gehen:
- Bilde die Wurzel. Ist das möglich, return false;
- verfahre wie gewohnt.Gäbe es dann auch noch gegenbeispiele?
-
Ja:
(49 * 49 * 49) mod 24 = 1Also müsste man, wenn überhaupt, alle n-ten Potenzen von Primzahlen ausschließen.
In diesem Fall wäre es 7^6.
-
77 klappt auch nicht. Aber bis 1000 wird jede Primzahl erkannt.
-
Man kann zeigen, dass fuer jede Primzahl p>3 gilt: p² % 24 = 1 (man verwendet dabei, dass fuer p>3 prim gilt es ex. k mit p = 6k +/-1). Der Test liefert also eine notwendige Bedingung fuer primheit.
Dummerweise wird auch jede Zahl, deren Primfaktoren alle > 3 sind als ergbnis der modulo rechnung 1 haben.
-
Hallo,
ich hab das auch bis 1000 geprüft und es zeigt definitiv ALLE Primzahlen mit anderen Zahlen an. Gibt es wirklich keine Möglichkeit, diese nicht-Primzahlen auszuschließen? Und asmodis: Kannst du mir einen Beweis für das p = 6k /-1 geben? Denn das scheint zu stimmen, nur ich weiß nicht warum.
MFG Toddy
-
Toddy, 6k +/-1 liefert dir nicht zwingend ein Primzahlenpaar (k=4).
-
Toddy schrieb:
Kannst du mir einen Beweis für das p = 6k /-1 geben? Denn das scheint zu stimmen, nur ich weiß nicht warum.
Das ist nicht schwer.
Jede Zahl ist von einer der folgenden 6 Formen:
6k => geht nicht, ist durch 6 teilbar
6k+1 => möglich
6k+2 => geht nicht, ist durch 2 teilbar
6k+3 => geht nicht, ist durch 3 teilbar
6k+4 => geht nicht, ist durch 2 teilbar
6k+5 (=6(k+1)-1) => möglich
-
D-U-D-E schrieb:
Toddy, 6k +/-1 liefert dir nicht zwingend ein Primzahlenpaar (k=4).
Das nicht, aber jede Primzahl über 3 ist entweder als 6k-1 oder als 6k+1 darstellbar.