Programmieren - alles kontrollieren 4.937 Themen, 20.655 Beiträge

Verfolgung starten Optionen

Primzahlen und Wahrscheinlichkeit

Olaf19 / 6 Antworten / Flachansicht Nickles

Hallo zusammen.

Streng genommen hat dieser Thread mehr mit Zahlen-Theorie zu tun als mit Programmierung - und doch finde ich ihn hier besser aufgehoben als auf "Allgemeines".

Folgende Überlegung: Einerseits gibt es unendlich viele Primzahlen, andererseits werden die Abstände zwischen benachbarten Primzahlen mit zunehmender Größe immer weiter. Logisch, denn je höher eine Zahl, desto mehr potentielle "echte Teiler" (=Teiler der Zahl mit Ausnahme ihrer selbst und der 1) gibt es. Anders ausgedrückt: Die Wahrscheinlichkeit, daß eine "sehr, sehr hohe Zahl" (was immer man darunter versteht ;-) eine Primzahl ist, wird immer geringer. Doch wie gering kann sie werden - gegen Null tendierend? Das kann nicht sein, denn es ist ja erwiesen, daß es unendlich viele Primzahlen gibt.

Gibt es also einen endlichen Grenzwert für die Wahrscheinlichkeit von Primzahlen?

Um dieser Frage auf den Grund zu gehen, hatte ich in den späten Achtziger Jahren auf dem Atari in Omikron Basic ein Programm geschrieben, daß ich jetzt noch einmal entwickeln möchte - höchstwahrscheinlich mit QBasic (mal gucken). Dieses Programm basierte auf folgendem Prinzip: Eine Primzahl ist eine Zahl, die durch keine andere Primzahl teilbar ist - sie läßt sich nicht durch 2, nicht durch 3, nicht durch 5, nicht durch 7 usw. teilen. Die Formel für die prozentuale Wahrscheinlichkeit W lautet demnach:

W = 100% * 1/2 * 2/3 * 4/5 * 6/7 * 10/11 * ...

Diese Zahl W wird also mit zunehmender Dauer der Berechnung immer kleiner; für jede neu entdeckte Primzahl P wird sie mit (P-1) / P multipliziert. Mein Atari hat damals Tage und Nächte ununterbrochen durchgerechnet - ich weiß schon gar nicht mehr, bis zu welchem Zahlenbereich ich vorgedrungen bin. Irgendwann habe ich die Rechnerei dann abgebrochen - der Wert für die Wahrscheinlichkeit W lag zu der Zeit bei 2,98%, Tendenz immer langsamer sinkend.

Okay - das alles z.B. mit QBasic wieder neu zu Programmieren, dürfte kein Problem darstellen. Aber vielleicht weiß darüber hinaus jemand von Euch eine mathematisch-logische Antwort auf die Frage: Geht die Wahrscheinlichkeit gegen Null, daß es sich bei einer beliebigen natürlichen Zahl um eine Primzahl handelt, oder gibt es dafür einen endlichen Grenzwert?

Sorry an alle, die's gelangweilt hat. Nächstes Mal poste ich wieder was Bodenständigeres - ich versprech's ;-)))

CU
Olaf19

Die Welt ist ein Jammertal ohne Musik. Doch zum Glueck gab es Bach, Beethoven, Haendel und Goethe (Helge Schneider)
bei Antwort benachrichtigen
Hallo Olaf, die Wahrscheinlichkeit strebt gegen asymptotisch gegen 0, wird ... Borlander
Hi Borlander, hat dieses Mal nicht geklappt mit der Antwort-Benachrichtigung ... Olaf19
ich hoffe, Du liest noch mit. Dank Antwortbenachrichtigung ja. Null darf ... Borlander
Komisch, jetzt habe auch ich eine Antwort-Benachrichtigung bekommen - doch ... Olaf19
Mrs. Software Olaf19 „Primzahlen und Wahrscheinlichkeit“
Optionen

Ausschnitt aus Encarta 2003, bitte alles lesen:

Primzahlen, eine Klasse von ganzen Zahlen größer als 1, die nur durch sich selbst und durch 1 teilbar sind.

Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, … Die bisher längste Primzahl mit über vier Millionen Stellen entdeckte der kanadische Mathematiker Michael Cameron 2001. Mit Hilfe weltumspannender Netzwerke von Personalcomputern gelang es Cameron, die Primzahl folgendermaßen zu berechnen:

2^13 466 917 -1.


Im Sommer 2002 stellten die drei indischen Mathematiker Manindra Agrawal, Neeraj Kayal und Nitin Saxena (Indian Institute of Technology, Kanpur) der Fachwelt einen leistungsfähigen Algorithmus vor, mit dessen Hilfe Computer erkennen können, ob es sich bei einer Zahl um eine Primzahl handelt oder nicht

Die Berechnung der Primfaktorzerlegung wird immer aufwendiger, je größer die Zahlen sind. Schon Carl Friedrich Gauß sagt in §329 seiner Disquisitiones Arithmeticae, „dass die Aufgabe, die Primzahlen von den zusammengesetzten zu unterscheiden und Letztere in Primfaktoren zu zerlegen, zu den wichtigsten und nützlichsten der gesamten Arithmetik gehört und die Bemühungen und den Scharfsinn sowohl der alten wie auch der neueren Geometer in Anspruch genommen hat”. Dieser Satz des Mathematikers ist auch heute noch uneingeschränkt richtig, wie auch seine weitere Aussage, dass die bisher angegebenen Methoden „mühsam und aufwendig” seien. Zwar lässt sich heute relativ schnell erkennen, ob eine Zahl eine Primzahl oder zusammengesetzt ist, doch ist bis heute kein Verfahren bekannt, das ähnlich schnell wie der euklidische Algorithmus die Primfaktorzerlegung selbst herstellen könnte. So kann man relativ leicht, sozusagen industriell in Minutenschnelle, 100-stellige Primzahlen p und q herstellen. Bildet man aber das Produkt m = pq zweier solcher Zahlen, so erhält man eine 200-stellige Zahl, für deren Zerlegung in die ursprünglichen Faktoren selbst die besten Computer etwa ein Milliarde Jahre rechnen müssten.

Microsoft® Encarta® Enzyklopädie Professional 2003 © 1993-2002 Microsoft Corporation. Alle Rechte vorbehalten.

bei Antwort benachrichtigen
Die Arbeit kannst du dir glaube ich sparen Olaf19