Google, Spiegel Online, Heise, Youtube, Translate, Amazon,

Das Problem mit den Primzahlen

Die Anzahl der Primzahlen bis zu einer gegebenen Zahl lässt sich bis ca. 10^10 relativ schnell rechnen. Es macht (zumindest mir) auch ein bisschen Spaß, zuzusehen, wie die Ergebnisse so dahinrauschen. Die ersten Millionen Primzahlen sind auf meiner 2.9GHz-Maschine mit 13 Sekunden relativ schnell gerechnet, doch mit zunehmender Größe der Zahlen, steigt auch der Rechenaufwand. Die Tabelle unten zeigt die Laufzeiten pro Millionen. Ab einer Million ist der Spaßfaktor dahin.

n-Millionste	Prim	Rechenzeit (s)	Zunahme
1	15.485.917	15	15
2	32.452.883	46	31
3	49.979.737	89	43
4	67.867.999	146	57
5	86.028.221	209	63
6	104.395.337	273	64
7	122.949.839	346	73
8	141.650.981	427	81
9	160.481.221	514	87
10	179.424.697	596	82
11	198.491.369	689	83
12	217.645.201	786	97

Der Code gibt jeweils nach 1000 geprüften Zahlen die Anzahl der gefundenen Primzahlen aus.

#include <stdio.h>
#include <math.h>
#include <limits>

#define U64 unsigned long long
int main(int, char**)
{
    FILE *fp    = stdout;
    fprintf(fp, "n; pi(n)\n");
    U64 c = 2LL;
    U64 i = 3LL;
    while( true )
    {
        i += 2LL;
        if( ! ((i-1LL) % 1000LL ) )
        {
             fprintf(fp, "%I64d;%I64d\n", i-1LL, c);
        }
        U64 u = (U64)sqrt(long double(i));
        U64 j = 3LL;
        while( i % j )
        {
            if( j > u )
            {
                c++;
                j = i;
            }
            else
            {
                j += 2LL;
            }
        }
    }
    fclose( fp );
    return 0;
}

Wahrscheinlich lässt sich die Laufzeit noch um einige Zehnerpotenzen verbessern. Zum Beispiel durch Assembler, Parallelität, usw. Doch selbst, wenn es gelingt, die Rechenzeit um einen Faktor 10^6 zu verbessern, also auf 15 Mikrosekunden herunter zu bekommen, bleibt das Problem an der Basis bestehen: Relativ schnell steigt der Rechenaufwand ins unendliche.

Die größte Zahl, die sich in einem 64-Bit-Register einer CPU darstellen lässt ist 2^64=18.446.744.073.709.551.615 (ca. 1.85 * 10^19). Das liegt ca. 10^9 Größenordnungen über der größten Prim in der Tabelle oben.

Die erste Prim darunter ist 18.446.744.073.709.551.557. Wenn von oben nach unten gesucht wird, müssen 58 Zahlen getestet werden. Auf meiner 2.9GHz CPU dauert das mit demselben Algorithmus ca. 22 Sekunden - wohlgemerkt zum Finden einer einzigen Primzahl. Wenn man davon ausginge, dass dies die nächsten Millionen so bleibt, was natürlich nicht der Fall ist, müsste man, wenn einem nichts besseres einfiele, auf das Ergebnis ca. 8 Monate warten (22Sekunden*1Mio/3600/24/30)

Primzahlenzahlen der Größenordnung 2^128 oder 2^2048 (ca. 3.2*10^616!) können mitnichten auf diese Weise gefunden werden. Hier müssen stärkere Geschütze aufgefahren werden und Erkenntnisse über endliche Mengen in Form von Restklassen-Algebra in die Überlegungen einfließen. Doch auch mit diesen High-End-Tricks sind die Grenzen schnell erreicht.

Einen ganz anderen Zugang zu den Primzahlen fand Riemann mit Vorarbeiten von Euler und Gaus. Es geht um die Abschätzung eines speziellen Fehlers in einer sehr speziellen Formel. Auf der einen Seite steht eine geometrische Reihe mit Dichten der Primzahlen und auf der anderen ein unendliches Produkt, das über alle Primzahlen gebildet wird.

...FF...