Project Euler 007 – Het 10.001ste priemgetal

Probleemstelling

De eerste zes priemgetallen zijn 2, 3, 5, 7, 11 en 13. Het zesde priemgetal is dus 13.

Bepaal het 10.001ste priemgetal.

Eerste analyse

We onderzoeken de getallen in stijgende volgorde, testen welke getallen priem zijn en houden bij hoeveel priemgetallen we hebben gevonden. Zodra de teller 10.001 bereikt, kennen we het antwoord.

Een getal $n$ is priem wanneer het groter is dan 1 en geen positieve delers behalve 1 en zichzelf heeft. Bij de controle hoeven we mogelijke delers slechts tot en met $\sqrt n$ te testen.

Gekozen programmeeraanpak

De oplossing gebruikt de twee functies priem(n) en nde_priem(n).

priem(n) gaat na of een gegeven getal priem is. De functie behandelt 2 afzonderlijk, verwerpt andere even getallen en test daarna alleen oneven delers.
nde_priem(n) doorloopt de oneven kandidaten in stijgende volgorde, roept priem aan en stopt zodra het gevraagde aantal priemgetallen gevonden is.

Algoritme

Tel 2 als het eerste priemgetal.
Onderzoek achtereenvolgens de oneven getallen 3, 5, 7, enzovoort.
Test voor elke kandidaat de oneven delers tot en met zijn vierkantswortel.
Verhoog de teller wanneer de kandidaat priem is.
Stop zodra de teller 10.001 bedraagt.

Python-programma

import time
from math import isqrt


def priem(n: int) -> bool:
    """Ga na of n een priemgetal is."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    # Een samengesteld getal heeft minstens een deler tot en met sqrt(n).
    for deler in range(3, isqrt(n) + 1, 2):
        if n % deler == 0:
            return False

    return True


def nde_priem(n: int) -> int:
    """Bereken het n-de priemgetal, waarbij 2 het eerste is."""
    if n < 1:
        raise ValueError("n moet minstens 1 zijn")
    if n == 1:
        return 2

    aantal_priemgetallen = 1
    kandidaat = 1

    # Na 2 hoeven alleen oneven kandidaten onderzocht te worden.
    while aantal_priemgetallen < n:
        kandidaat += 2
        if priem(kandidaat):
            aantal_priemgetallen += 1

    return kandidaat


# Start van de tijdsmeting
starttijd = time.perf_counter()


# Bereken het 10.001ste priemgetal
antwoord = nde_priem(10_001)


# Stop de tijdsmeting
eindtijd = time.perf_counter()
uitvoeringstijd = eindtijd - starttijd


# Toon het resultaat
print(f"Het 10.001ste priemgetal is: {antwoord}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

De eenvoudige bovengrens voor de tijdscomplexiteit is $O(p_n\sqrt{p_n})$ , waarbij $p_n$ het $n$ -de priemgetal is. Het geheugengebruik is $O(1)$ .

Wiskundige benadering

De priemgetal-telfunctie $\pi(x)$ telt hoeveel priemgetallen kleiner dan of gelijk aan $x$ zijn. Volgens de priemgetalstelling geldt

$\pi(x)\sim\frac{x}{\ln x}.$

Voor de omgekeerde vraag kunnen we gebruiken dat

$p_n\approx n(\ln n+\ln\ln n-1).$

Voor $n=10\,001$ geeft dit ongeveer 104.318. We verwachten het antwoord dus in de buurt van honderdduizend. Dit is een schatting; de exacte primaliteitstesten van het programma blijven nodig.

Resultaat

Het 10.001ste priemgetal is

$\boxed{104743}.$

Uitvoeringstijd: 0,05393281 seconden.

Besluit

De opsplitsing in priem(n) en nde_priem(n) levert een duidelijke en herbruikbare oplossing. Proefdeling is voor deze opgave ruim snel genoeg, terwijl de priemgetalstelling vooraf een goede schatting van de grootteorde geeft.