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.

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 = 2;
    U64  i = 3;
    while( true )
    {
        i += 2LL;
        if( ! ((i-1LL) % 1000LL ) )
        {
             fprintf(fp, "%lld;%lld\n", i, c);
        }
        U64 u = (U64)sqrtl(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.