Project Euler 010 – Som van priemgetallen

Probleemstelling

De priemgetallen kleiner dan 10 zijn 2, 3, 5 en 7. Hun som is 17.

Bereken de som van alle priemgetallen die strikt kleiner zijn dan twee miljoen.

Eerste analyse

Een natuurlijke aanpak onderzoekt elk getal afzonderlijk op primaliteit en telt de priemgetallen op. Het getal 2 is het enige even priemgetal. We beginnen daarom met som 2 en onderzoeken met is_priem alleen de oneven getallen van 3 tot en met 1.999.999: precies 999.999 kandidaten.

De priemtest probeert oneven delers tot en met de gehele vierkantswortel van de kandidaat. Zodra een deler gevonden is, stopt de test. Vooral priemgetallen vragen veel deelbaarheidstesten, want daarbij moet de volledige lus doorlopen worden.

Twee programmeermethoden

Methode 1: elk oneven getal testen

Het eerste programmadeel telt 2 apart mee. Voor ieder volgend oneven getal roept ze is_priem aan en telt ze het getal alleen op als de test True geeft. Deze methode vraagt weinig geheugen, maar herhaalt veel deelbaarheidstesten.

Methode 2: de zeef van Eratosthenes

Het tweede programmadeel maakt een tabel met voor elk getal een aanduiding of het nog kandidaat-priem is. Bij elk gevonden priemgetal worden de veelvouden geschrapt. Daarna tellen we de overblijvende priemgetallen op. De zeef bewaart informatie over alle kandidaten en vermijdt zo de afzonderlijke deelbaarheidstesten.

Algoritme van de zeef

We voeren beide methoden uit en vergelijken hun antwoord en uitvoeringstijd. Voor de zeef volgen we deze stappen:

Maak een tabel voor de getallen van 0 tot en met 1.999.999; markeer aanvankelijk alle posities als mogelijk priem.
Markeer 0 en 1 als niet-priem.
Doorloop de getallen van 2 tot en met 1414, de gehele vierkantswortel van 1.999.999.
Is een getal $p$ nog niet geschrapt, schrap dan $p^2,p^2+p,p^2+2p,\ldots$ , zolang ze onder twee miljoen liggen.
Tel alle getallen op waarvan de markering nog waar is.

De tijdsmeting voor de zeef omvat ook het opbouwen van de tabel. Voor deze invoer is de zeef de aangewezen methode om alle priemgetallen tegelijk te vinden. De eerste methode blijft behouden als eenvoudige vergelijking en onafhankelijke controle.

Wiskundige achtergrond

Eratosthenes en zijn zeef

Eratosthenes van Cyrene leefde ongeveer van 276 tot 194 v.Chr. Deze Griekse geleerde werkte in Alexandrië en stond er aan het hoofd van de beroemde bibliotheek. Hij is ook bekend door zijn bepaling van de omtrek van de aarde. De zeef die zijn naam draagt, is een methode om priemgetallen systematisch te vinden.

Het beeld van een zeef helpt om de werking te onthouden: de samengestelde getallen worden weggefilterd, de priemgetallen blijven over. Het oude wiskundige idee laat zich rechtstreeks vertalen naar een tabel en lussen in Python.

Een voorbeeld: priemgetallen kleiner dan 30

We beginnen met de getallen 2 tot en met 29.

Stap	Nieuw geschrapte getallen
Veelvouden van 2, vanaf 4	4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28
Veelvouden van 3, vanaf 9	9, 15, 21, 27
4 is geschrapt	Geen nieuwe stap nodig
Veelvouden van 5, vanaf 25	25

Bij 3 wordt ook bijvoorbeeld 12 bezocht, maar dat was al geschrapt. De tabel toont alleen de nieuwe schrappingen. Omdat $6^2>29$ , zijn we klaar. Er blijven

$2,3,5,7,11,13,17,19,23,29$

over. Hun som is 129.

Waarom volstaan delers tot de vierkantswortel?

Als $n$ samengesteld is, kunnen we $n=ab$ schrijven met $1<a\le b$ . Dan is $a^2\le ab=n$ , dus $a\le\sqrt n$ . Het getal $a$ heeft een priemdeler $p\le a$ . Elk samengesteld getal $n$ heeft bijgevolg een priemdeler $p\le\sqrt n$ .

Daarom hoeft is_priem geen grotere delers te proberen. Om alle samengestelde getallen onder $N$ te schrappen, volstaan op dezelfde manier de priemgetallen tot en met $\lfloor\sqrt{N-1}\rfloor$ . isqrt berekent die gehele vierkantswortel zonder afrondingsfouten.

Waarom beginnen bij het kwadraat?

Een kleiner veelvoud $kp$ met $2\le k<p$ heeft een priemdeler van $k$ die kleiner is dan $p$ . Het werd dus al in een eerdere zeefstap geschrapt. Het eerste veelvoud dat nog niet noodzakelijk geschrapt is, is $p^2$ . Het getal $p$ zelf blijft staan.

Waarom blijven precies de priemgetallen over?

Een priemgetal wordt nooit geschrapt: elke schrapping betreft een product van twee getallen groter dan 1. Omgekeerd heeft elk samengesteld getal onder $N$ een priemdeler binnen het onderzochte bereik en wordt het bij die priemdeler geschrapt. Een nog niet geschrapte kandidaat in de buitenste lus is dus zelf priem. De overblijvende getallen zijn precies alle priemgetallen onder de grens.

Python-programma

We meten beide methoden één keer. is_priem probeert oneven delers tot de vierkantswortel. De zeef schrapt veelvouden vanaf het kwadraat van elk priemgetal.

import time
from math import isqrt


def is_priem(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    for deler in range(3, isqrt(n) + 1, 2):
        if n % deler == 0:
            return False
    return True


grens = 2_000_000

# Methode 1: test elk oneven getal en tel de priemgetallen op.
start = time.perf_counter()
som = 2
for getal in range(3, grens, 2):
    if is_priem(getal):
        som += getal
tijd_priemtest = time.perf_counter() - start
print(f"Priemtest: {som}, tijd: {tijd_priemtest:.3f} s")

# Methode 2: schrap de veelvouden en tel de overblijvende getallen op.
start = time.perf_counter()
zeef = [True] * grens
zeef[0] = zeef[1] = False
for p in range(2, isqrt(grens - 1) + 1):
    if zeef[p]:
        for veelvoud in range(p * p, grens, p):
            zeef[veelvoud] = False

som = 0
for getal in range(2, grens):
    if zeef[getal]:
        som += getal
tijd_zeef = time.perf_counter() - start
print(f"Zeef: {som}, tijd: {tijd_zeef:.3f} s")
print(f"De zeef is {tijd_priemtest / tijd_zeef:.1f} keer sneller.")

Snelheidsvergelijking en resultaat

Beide methoden geven 142913828922. Eén uitvoering van dit programma gaf:

Methode	Tijd
Oneven getallen testen	3,662 s
Zeef van Eratosthenes	0,390 s

De zeef was hier ongeveer 9,4 keer sneller. De tijden omvatten het berekenen en optellen; ze verschillen per computer en uitvoering.

Besluit

De som van alle priemgetallen kleiner dan twee miljoen is 142913828922. Afzonderlijke priemtesten leveren een eenvoudige oplossing met weinig geheugen. De zeef van Eratosthenes is hier aanzienlijk sneller doordat ze de samengestelde getallen gezamenlijk schrapt, ten koste van een tabel in het geheugen.