Primzahl-Aufgabe

Toddy

Hallo,

Ich muss eine Aufgabe machen, die folgendermaßen lautet:

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?

MFG Toddy

Bashar

Wieso versuchst du's nicht erstmal selbst? Es müssen ja nicht gleich 1200 Zeilen werden ...

Mario Sandler

Toddy schrieb:

dass das programm dann bei einem PC mit 10 MHz Prozessor ruckelfrei läuft^^.

Ruckelfrei? Willst du einen Ego-Shooter
oder ein Primzahlen Programm haben?

http://de.wikipedia.org/wiki/Primzahltest
Hier solltest du einige (mehr oder weniger)
effektive Algorithmen finden.

Jester

Storm.Xapek.de schrieb:

http://de.wikipedia.org/wiki/Primzahltest
Hier solltest du einige (mehr oder weniger)
effektive Algorithmen finden.

Effektiv sind sie hoffentlich alle.
Aber manche sind effizienter als andere.

.filmor

Jester schrieb:

Effektiv sind sie hoffentlich alle.

Da sind aber auch Monte-Carlo-Algorithmen dabei

D-U-D-E

Sind randomisierte Algorithmen von Haus aus nicht effektiv?

borg

D-U-D-E schrieb:

Sind randomisierte Algorithmen von Haus aus nicht effektiv?

filmor wollte darauf hinaus das monte carlo algorithmen nicht immer korrekte ergebnisse liefern, sondern nur mit einer hohen wahrscheinlichkeit. man unterscheidet da zwischen monte carlo und las vegas algorithmen, letztere sind auch randomisiert, sie liefern aber trotzdem immer korrekte ergebnisse.
man kann also nicht sagen das randomisierte algorithmen von haus aus nicht effektiv sind.

edit: mir würde jetzt allerdings kein las-vegas-primzahltest einfallen, ein beispiel für einen las-vegas algorithmus wäre ein quicksort wo die auswahl des pivotelements randomisiert ist.

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.