Hallo, wie kann ich bei einer grossen Zahl schnell erkennen, ob es sich um eine Primzahl handelt? (gib es da irgendwelche Regeln)
Gruss Mirco
Hallo, wie kann ich bei einer grossen Zahl schnell erkennen,
ob es sich um eine Primzahl handelt? (gib es da irgendwelche
Regeln)
leider nein. Es gibt keinen schnellen Algorithmus, der verr"at ob eine Zahl eine Primzahl ist.
Du musst also testen, ob sie durch eine Primzahl
Es gibt keinen schnellen Algorithmus, der verr"at
ob eine Zahl eine Primzahl ist.
Du musst also testen, ob sie durch eine Primzahl
Hallo, wie kann ich bei einer grossen Zahl schnell erkennen,
ob es sich um eine Primzahl handelt? (gib es da irgendwelche
Regeln)Gruss Mirco
Versuch den Primzahlchecker:
http://ema.bonn.de/primzahl.htm
Gruß
Rainer
Versuch den Primzahlchecker:
http://ema.bonn.de/primzahl.htm
Versuch ihn lieber nicht. Das Programm ist eine Frechheit. Anstatt zu sagen, ob die Zahl eine Primzahl ist, gibt sie nacheinander jede Primzahl aus, durch die sie teilbar ist und zwar jedesmal mit einem eigenen Dialog. Wenn Du eine hinreichend große Zahl eingibst, mußt Du klicken bis der Finger abstirbt oder den Browser mit Gewalt abschießen.
leider nein. Es gibt keinen schnellen Algorithmus, der verr"at
ob eine Zahl eine Primzahl ist.
Hallo Michaela,
das stimmt nicht: Es gibt schnelle Algorithmen zum Primzahltesten.
Du weißt vielleicht, daß die heute üblichen Verschlüsselungssysteme (PGP etc.) auf Produkten aus zwei großen Primzahlen beruhen. Bei der Generierung eines solchen Schlüssels muß also von dem betreffenden Programm festgestellt werden, ob eine große (z. B. 64 oder 128 Bit lange) Zufallszahl prim ist oder nicht. Diese Algorithmen arbeiten nun aber nicht so, daß sie beginnend von 3 bis Wurzel(Zufallszahl) alle ungeraden Zahlen als eventuelle Teiler durchchecken – dabei würde man sich in der Tat schwarzrechnen –, sondern sie testen nur mit einer vergleichweisen geringen Menge an potentiellen Teilern, wobei dies aber besonders „ausgesuchte“ Zahlen sind, in dem Sinne, daß sie bei einem Fehlschlag der Teilung (Rest > 0) ein starkes Indiz darauf liefern, daß die Zahl prim ist. Diese Algorithmen werden als „probabilistische Primzahltests“ bezeichnet. Sie können in der Tat „nur“ mit einer gewissen Wahrscheinlichkeit bestimmen, ob eine gegebene Zahl prim ist, aber diese Wahrscheinlichkeit kann beliebig groß („1–10^–x“) gemacht werden (es gibt Tests, bei denen die Wahrscheinlichkeit eines Irrtums kleiner ist als die eines Hardwarefehlers(!) während der Laufzeit). Was diese Algorithmen alle nicht liefern, ist die Primfaktorzerlegung einer nicht-primen Zahl; für diese Aufgabe gibt es tatsächlich keinen schnellen Algorithmus (gäbe es einen, wäre den Verschlüsselungssystemen ihre Grundlage entzogen).
Es ist also wichtig, zwischen der Frage „Ist die Zahl N prim?“ und der Frage „Wie lautet die Faktorisierung der Zahl N?“ zu unterscheiden. Die erste ist auch für große Zahlen schnell zu beantworten, die zweite nicht.
Mit freundlichem Gruß
Martin
1 „Gefällt mir“
Natürlich sagt es, ob die Zahl eine Primzahl ist, gib mal 7 rein.
Die Teilerei kommt nur bei Nicht-Primzahlen und ist so gewollt.
Ist allerdings bei großen Zahlen etwas lästig, stimmt 
Gruß
Rainer
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo, wie kann ich bei einer grossen Zahl schnell erkennen,
ob es sich um eine Primzahl handelt? (gib es da irgendwelche
Regeln)
Es gibt den kleinen Fermatschen Satz:
Ist p prim und a natürliche Zahl mit 1p-1 = 1 (mod p)
Das folgende Verfahren wird als Fermat-Test bezeichnet:
- Wähle ein a p-1 (mod p)
- kommt nicht 1 raus, so ist p keine Primzahl. Fertig.
- kommt 1 raus, so ist p vielleicht eine Primzahl. In diesem Fall kann man dasselbe ja noch mit anderen a’s wiederholen, bis man entweder rausgekriegt hat, dass p nicht prim ist, oder bis einem die Wahrscheinlichkeit dafür, dass es eine Primzahl ist, hoch genug erscheint.
Das ist zwar nur ein probabilistischer Algorithmus, aber immerhin.
leider nein. Es gibt keinen schnellen Algorithmus, der verr"at
ob eine Zahl eine Primzahl ist.Hallo Michaela,
das stimmt nicht: Es gibt schnelle Algorithmen zum
Primzahltesten.
und wie funktioniert der? wo kann man sowas nachlesen (ich würde gerne selber mal sowas programmieren)
Grüße
Moritz