Primzahl-Aufgabe

D-U-D-E

Ok, ich hab unglücklich verallgemeinert

Ich habe aus filmors Aussage geschlossen, daß Monte Carlo Algorithmen nicht effektiv sind, und wollte nur mal nachhacken. Monte Carlo/Las Vegas Algorithmen sind mir schon ein Begriff.

Ein Las Vegas Primzahltest wäre die Zahlen von 2 bis n-1 (randomisiert) durchzugehen und auf Teilbarkeit prüfen. Ich gebs zu, daß dieser Algorithmus nicht gerade der effizienteste ist Korrigiert mich, wenn ich falsch liege.

Mr.Fister

Es genügt auf jeden Fall, die ungeraden Zahlen zwischen einschl. 3 und floor(sqrt(n)) sowie die 2 auf Teilbarkeit zu prüfen.

CStoll

Storm.Xapek.de schrieb:

Hier solltest du einige (mehr oder weniger)
effektive Algorithmen finden.

Du kennst den Unterschied zwischen effektiv (das Verfahren erreicht sein Ziel) und effizient (Minimierung von Rechendauer, Speicherbedarf etc)?

@DUDE: Dein Ansatz dürfte sich in der Effizienz nicht wesentlich vom Brute-Force-Ansatz unterscheiden (bei einer Primzahl mußt du auf jeden Fall alle Teiler-Kandidaten überprüfen, bei einer zusammengesetzten Zahl hängt es vom Glück ab, wie schnell du einen Teiler findest) - und wenn, ist er eher aufwendiger, weil du mitschreiben mußt, welche Zahlen du schon geprüft hast.

matimatiker

Man gibt eine Zahl ein und es wird angezeigt ob dies eine Primzahl ist. Dabei soll so viel! wie möglich unnötige Rechenarbeit gespart werden. man kann sich das so vorstellen, dass das programm dann bei einem PC mit 10 MHz Prozessor ruckelfrei läuft^^. Kann mir jemand einen Algorithmus oder den Quellcode aufschreiben?

nimm eine vorberechnete, sortierte primzahlenliste

*gt*Bocky*lt*

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
}

Toddy

Hallo,

ich weiÃŸ nicht ob ichs richtig verstanden habe, aber wenn man dort zb. 3 einsetzt kommt 9$ raus und das ergibt 9. 3 ist aber eine Primzahle.

MFG toddy

Black Shadow

Toddy schrieb:

Hallo,

ich weiÃŸ nicht ob ichs richtig verstanden habe, aber wenn man dort zb. 3 einsetzt kommt 9$ raus und das ergibt 9. 3 ist aber eine Primzahle.

MFG toddy

Bei Stichproben scheint es bei Zahlen >=5 zu klappen. Wie das funktioniert weiß ich jetzt auch net

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.