Der Primzahlsatz
Die Anzahl von Primzahlen
Die Anzahl der Primzahlen in einem Zahlenbereich lässt sich relativ genau abschätzen. Man verwendet hierzu den sogenannten Primzahlsatz.
In der Abbildung sind folgende Graphen dargestellt:
roter Graph: n -> Anzahl der Primzahlen kleiner oder gleich n grüner Graph: n -> n/ln(n)
Man erkennt, dass der grüne Graph den roten recht gut annähert bzw. dass die Anzahl der Primzahlen, die kleiner oder gleich n sind, ungefähr n/ln(n) beträgt.
Diese Zusammenhänge sollen jetzt mit einer geeigneten Funktion überprüft werden.
Entwicklung einer Anzahlfunktion
Ziel ist es, eine Funktion zu entwickeln, mit der man die Anzahl der Primzahlen ermitteln kann, die kleiner oder gleich einer übergebenen Zahl sind.
Aufgabe 1
(a) Benutze die Funktion istPrimzahl
als Baustein, um eine Funktionsdefinition für die Funktion anzahlPrimzahlen
zu entwickeln.
def anzahlPrimzahlen(n):
"""
Verhalten:
Übergabe: natürliche Zahl n
Rückgabe: Anzahl der Primzahlen, die kleiner oder gleich n sind
Testfälle:
>>> anzahlPrimzahlen(2)
1
>>> anzahlPrimzahlen(10)
4
>>> anzahlPrimzahlen(100)
25
"""
...
if __name__ == "__main__":
from doctest import testmod
testmod(verbose=True)
(b) Bestimme mit der entwickelten Funktion weitere Anzahlen und vergleiche mit der Abschätzung.
>>> from math import log
>>> 100/log(100)
21.71472409516259
Aufgabe 2
Manchmal hört man den Vorschlag, Primzahlen in einer Primzahldatenbank zu sammeln. In diese Datenbank sollten dann natürlich auch die Primzahlen kommen, die heutzutage beim Aufbau von Kryptosystemen benutzt werden.
Moderne Kryptosysteme benutzen Primzahlen mit mehr als 300 Stellen. Schätze mit dem Primzahlsatz ab, wie viele Primzahlen es in diesem Bereich gibt. Betrachte hierzu den Bereich zwischen 21000 und 21001. Mit Python kann man schnell eine Vorstellung von der Größe dieser Zahlen gewinnen:
>>> 2**1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
>>> len(str(2**1000))
302
>>> 2**1001
21430172143725346418968500981200036211228096234110672148875007767407021022498722449863967576313917162551893458351062936503742905713846280871969155149397149607869135549648461970842149210124742283755908364306092949967163882534797535118331087892154125829142392955373084335320859663305248773674411336138752
>>> len(str(2**1001))
302
So könntest du vorgehen:
>>> n1 = 2**1000
>>> n2 = 2**1001
...
Beurteile mit dem gewonnenen Ergebnis den oben gemachten Vorschlag. Zur Information: Die Anzahl der Atome im Universum liegt Schätzung zufolge im Bereich zwischen 1084 und 1089.
Quellen
- [1]: Primzahlsatz - Urheber: Noel Bush - Lizenz: Creative Commons BY-SA 3.0