Primzahl-Aufgabe

Bocky< schrieb:
Eine andere Möglichkeit zu Berechnung von Primzahlen ist folgende:
if( ( (primzahl*primzahl) %24 ) == 1 )
{
  return true; //Ist eine Primzahl
}
else{
  return false;//Ist keine Primzahl
}

Das scheint echt zu klappen!
Wie kann das sein?? Es muss Gegenbeispiele geben.
Wenn das so einfach wäre, könnte man sich das ganze Primzahl-Gesuche sparen.

asmodis

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.

Black Shadow

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 = 1

Also müsste man, wenn überhaupt, alle n-ten Potenzen von Primzahlen ausschließen.
In diesem Fall wäre es 7^6.

asmodis

77 klappt auch nicht. Aber bis 1000 wird jede Primzahl erkannt.

asmodis

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.

Toddy

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

D-U-D-E

Toddy, 6k +/-1 liefert dir nicht zwingend ein Primzahlenpaar (k=4).

Jester

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

CStoll

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.