Wenn wir die ersten 6 Primzahlen auflisten, erhalten wir:

2, 3, 5, 7, 11, 13

Die 6-te Primzahl ist also 13.

Was ist die 10001-te Primzahl?

Lösung

Wir nutzen die folgenden Tatsachen:

1 ist keine Primzahl.
Alle Primzahlen außer 2 sind ungerade.
Jede Zahl kann höchstens einen Primfaktor haben, der größer als ihre Wurzel ist.

Matlab-Code:

gesucht = 10001;
letztePrimzahl = 2;
nummer = 1;
test = 3;

while nummer < gesucht
    wurzel = floor(sqrt(test));
    istPrim = 1;
    for teiler = 3 : 2 : wurzel
        if mod(test, teiler) == 0
            istPrim = 0;
        end
    end
    if istPrim == 1
        nummer = nummer + 1;
        letztePrimzahl = test;
    end
    test = test + 2;
end

letztePrimzahl

Ergebnis: 104743
Rechenzeit: 0.449584 Sekunden