Primzahlen

Wissenschaft Physik
#1

Hallo!

Ich habe ein paar Fragen zum Thema Primzahlen!

  1. Gibt es eine Formel, um aus gegebenen Primzahlen neue Primzahlen zu berechnen?

  2. An alle, die von Informatik Ahnung haben: Wenn ich überprüfen will, ob eine Primzahl eine Primzahl ist, bleibt mir ja nichts anderes übrig, als sie einmal durch alle Zahlen, die vor ihr kommen, zu teilen und zu gucken, ob es auch wirklich keine Zahl gibt, durch die sie teilbar ist. Somit ist ein Algorithmus, der berechnen soll, ob eine Zahl eine Primzahl ist von der Komplexität O( 2^n ) ( big-O ) - weiß jemand, ob das Problem des Primzahlen - Tests NP-vollständig ist?

Florian

#2

Sorry! Fehler!
Ist natürlich quatsch - der Algorithmus hat die Komplexität O( n ) - war ein Denkfehler :wink:

#3

Hallo Florian,

  1. Gibt es eine Formel, um aus gegebenen Primzahlen neue
    Primzahlen zu berechnen?

Nein. Es gibt weder eine Formel, die nur Primzahlen ausspuckt, noch eine Formel, die aus einer gegebenen Primzahl eine weitere berechnet. Fermat glaubte, mit „2^(2^n) + 1“ (n = 1, 2, 3…) eine Nur-Primzahlen-liefernde Formel gefunden zu haben. Sein Traum zerrann nach seinem Tod, als Euler eine Zerlegung für die fünfte Fermat-Zahl fand: 4294967297 = 641 * 6700417. Euler selbst hat dafür auch eine „Primzahl-Formel“ gefunden: x^2 + x + 41 liefert für x = 41 bis 80 nur Primzahlen!

  1. An alle, die von Informatik Ahnung haben: Wenn ich
    überprüfen will, ob eine Primzahl eine Primzahl ist, bleibt
    mir ja nichts anderes übrig, als sie einmal durch alle Zahlen,
    die vor ihr kommen, zu teilen und zu gucken, ob es auch
    wirklich keine Zahl gibt, durch die sie teilbar ist.

Du mußt nur ungerade k (k = potentieller Teiler) testen und mit k nur bis sqrt(n) gehen (denn wenn ein Teiler existiert, der größer als sqrt(n) ist, dann muß der zugehörige Partner kleiner als sqrt(n) sein und wäre bereits gefunden worden).

Mit freundlichem Gruß
Martin

#4

Hallo,

Du mußt nur ungerade k (k = potentieller Teiler) testen

Eigentlich sogar nur die Priemzahlen. Die Frage ist wohl, was einfacher und schneller zu implementieren ist.

Cu Rene

#5

Hallo!

Du mußt nur ungerade k (k = potentieller Teiler) testen und
mit k nur bis sqrt(n) gehen (denn wenn ein Teiler existiert,
der größer als sqrt(n) ist, dann muß der zugehörige Partner
kleiner als sqrt(n) sein und wäre bereits gefunden worden).

Wenn man von den Primzahlen ausgeht, die nach der 7 kommen, so muß man nur k für 1,3,7 und 9 überprüfen - 5 ist unnötig, oder?.

Florian

#6

Du mußt nur ungerade k (k = potentieller Teiler) testen und
mit k nur bis sqrt(n) gehen (denn wenn ein Teiler existiert,
der größer als sqrt(n) ist, dann muß der zugehörige Partner
kleiner als sqrt(n) sein und wäre bereits gefunden worden).

Wenn man von den Primzahlen ausgeht, die nach der 7 kommen, so
muß man nur k für 1,3,7 und 9 überprüfen - 5 ist unnötig,
oder?.

Sorry, ich verstehe Deine Frage und ihren Zusammenhang mit meinem Hinweis auf „sqrt(n)“ nicht. Bitte formuliere sie neu.

#7

Hi,

ein paar Algorithmen zur Primzahlsuche findest du hier:
http://rhlx01.rz.fht-esslingen.de/projects/krypto/pr…

Wir haben in unserem Studium Primzahlen mit dem von Martin genannten Algorithmus (Sieb des Eratosthenes) erzeugt.
Dazu haben wir einen „virtuellen“ Parallelrechner verwendet, bei dem sich jeder Prozessor mit einem der Teiler beschäftigte.

Das Prinzip genauer erklärt, denn man könnte diesen Alg. auch schön unter Linux mit mehreren Prozessen implementieren:

Es sollen alle Primzahlen in der Zahlenmenge 1…n ermittelt werden. Dazu müssen lediglich alle Vielfachen der Zahlen von 1 bis sqrt(n) eliminiert werden. 1 ist keine Primzahl, also kann man die gleich mal von Haus aus weglassen (ich schreibe aber trotzdem immer 1…n).
Man stellt sich also eine Zahlenkette vor, die wie an einem Fließband (Pipelining) alle einzelnen Prozesse durchläuft.

Jeder Prozess erhält eine eindeutige Zahl und eliminiert alle ihm gegebenen Zahlen, die durch diese Zahl teilbar sind. Alle anderen reicht er an seinen Nachfolger weiter.

-> 2 -> 3 -> 5 -> …

Prozess 2 eliminiert alles, was durch 2 teilbar ist. Dies kann man eigentlich weglassen und sich den Rechenaufwand sparen indem man in der Schleife 1…n nur alle ungeraden Zahlen übergibt.
Also besser:

-> 3 -> 5 -> 7 -> …

Der erste Prozess erhält also die Kennzahl 3 und eliminiert alles, was durch 3 teilbar ist. Prozess 5 alles, was durch 5 teilbar usw.

Am Anfang weiß man natürlich nicht, welche Prozesse man benötigt. Hier war es ja recht einfach, weil dies die wohl bekanntesten Primzahlen sind.
Die Prozesse werden also dynamisch generiert.

Pseudo-Code im Prozess:

  • eliminiere alle Zahlen, die Vielfache meiner Kennziffer sind
  • erhalte ich eine Zahl, die ich weitergeben werde, und ich tue dies zum ersten Mal, dann erzeuge einen Nachfolgeprozess, der alle Vielfachen dieser Zahl eliminiert (diese Prozesserzeugung ist durch sqrt(n) eingeschränkt)
  • ansonsten Zahl weitergeben

Es werden also x Prozesse erzeugt, der letzte Prozess arbeitet mit einer Kennziffer

#8

Hallo!

Tud mir leid, ich habe gemerkt das ich dich mißverstanden habe…was ich sagen wollte, ist: wenn man von den Zahlen, die größer als 10 sind, ausgeht, können nur Zahlen, die auf 1,3,7 oder 9 enden Primzahlen sein…du hast aber nicht von den potentiellen Primzahlen, sondern von den Zahlen, die eine Primzahlen teilen können, geredet.

Florian

#9

Hi.

Du mußt nur ungerade k (k = potentieller Teiler) testen

Das stimmt so nicht ganz. Die 2 muss auch getestet werden. Oder wie willst du sonst rausfinden, dass 1024 keine Primzahl ist?

Sebastian.

#10

Das stimmt so nicht ganz. Die 2 muss auch getestet werden.

Nein, eigentlich nicht. Jeder vernünftige Algorithmus zur Primzahlbestimmung schließt gerade Zahlen > 2 explizit aus, da es offentlich keine Primzahlen sein können. Ein Algorithmus, der auch gerade Zahlen testet, erhöht die Rechenzeit unnötig.
Rein formal hast du natürlich recht…

Gruß,

Markus

#11

Das stimmt so nicht ganz. Die 2 muss auch getestet werden.

Auch hi,

ich gebe unumwunden zu, daß ich unaufmerksamerweise vergessen habe, das hinzuzufügen. Bei Digitalrechnern, deren ALU im Zweiersystem arbeitet (also praktisch alle), muß die 2 allerdings nicht „als solche“ getestet werden (heißt: man muß die ALU nicht mit der Operation „MOD 2“ beauftragen), sondern man kann am niedrigsten Bit „sofort“ (heißt: durch eine „billige“ Logikoperation) erkennen, ob die Zahl gerade oder ungerade ist. Das soll jetzt aber keine Entschuldigung sein.

Danke für Deinen Hinweis.

Mit freundlichem Gruß
Martin

#12

Hi!

Ich denke, so ungefähr hab’ ich dich verstanden :wink: - dankesehr für die ausführliche Beschreibung!

Florian