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 2¹⁰⁰⁰ und 2¹⁰⁰¹. 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 10⁸⁴ und 10⁸⁹.