Primzahlen und Primfaktor < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:36 Mo 21.01.2008 | | Autor: | Mephis |
| Aufgabe | Mit n := [mm] \produkt_{i=1}^{r} p_{i} [/mm] kann man eine Folge von unendlich vielen Primzahlen p1, p2, . . . konstruieren:
Wähle p1 := 2 und pn+1 als den kleinsten Primfaktor der folgenden Zahl:
p1 · p2 · . . . · pn + 1
a) Bestimmen Sie p2 bis p7.
b) Diskutieren Sie, ob dieser Algorithmus für die Praxis geeignet ist.
|
Hallo Leute,
irgendwie verstehe ich wohl die Frage nicht wirklich.
Meine Idee ist:
![[]](/images/popup.gif) Tabelle als Bild
Ich brauche dringend Euren Rat, da ich am verzweifeln bin, keine Ahnung habe, ob es so richtig ist und die Aufgabe Morgen abgeben muss.
Und was ist mit Teil b)?
Vielen Dank im Voraus
Meph
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:44 Mo 21.01.2008 | | Autor: | Zorba |
Sieht gut aus! Zu b) würde ich schreiben, dass dieser Algorithmus sehr schnell sehr aufwändig wird, da schon für relativ kleine n ziemlich große Zahlen untersucht werden müssen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:59 Mo 21.01.2008 | | Autor: | leduart |
Hallo
a)Deine Tabelle ist richtig, (dabei setz ich vorraus, dass du richtig multipl. hast.
b) kommt drauf an, was die Praxis will: sicher Primzahlen erzeugen: ja.
eine vollständige Zahl etwa der Primzahlen bis 100: Nein.
2. die Primzahlen werden seeehhhr schnell sehr groß, d.h. Stellenzahl normaler Rechner wird schnell überschritten!
(nachdem man 2,3,5,7 hat, also nach dem 7. Schritt, werden sie in jedem Schritt mindestens eine Zehnerpotenz größer usw.)
Gruss leduart
|
|
|
| |
|
Zum theoretischen Wert der Aussage: Da benachbarte natürliche Zahlen teilerfremd sind, wird mit dem Algorithmus keine Primzahl zweimal gefunden, es sind also potentiell unendlich viele. Der Informationswert der Aussage ist aber sehr mager: sie besagt nicht mehr, als dass eine beliebige natürliche Zahl entweder prim oder zusammengesetzt ist. In jedem Fall muss sie zuerst in Primfaktoren zerlegt werden, was bereits die Kenntnis der Primeigenschaft dieser Faktoren voraussetzt. Letztenendes könnte man genauso gut immer größere Primzahlen aufschreiben. Die Frage nach der Eignung des Algorithmus "für die Praxis" ist unklar: was heißt "für die Praxis"? Wenn es nur um das Finden großer Primzahlen geht, ist das rasche Anwachsen der Zahlen nicht unbedingt von Nachteil. Das eigentliche Problem besteht im Faktorisieren sehr großer Zahlen.
Aus der Tatsache, dass benachbarte natürliche Zahlen teilerfremd sind, kann man noch folgendes ableiten: Sei p# = 2*3*5*...*p. Dann sind p# und p#+1 teilerfremd, und zur Feststellung der Primeigenschaft von p#+1 sind nur noch Probedivisionen durch Primzahlen q nötig, für die gilt:
p < q < Wurzel(p#+1).
|
|
|
|
![[]](http://www.hxk-raid.de/upload/prim.gif){kind=small}
Tabelle als Bild