Project Euler 003 – Grootste priemfactor

Probleemstelling

De priemfactoren van 13195 zijn 5, 7, 13 en 29.

Wat is de grootste priemfactor van het getal 600851475143?

Eerste analyse

Alle getallen tot 600851475143 testen zou bijzonder traag zijn. Met proefdeling hoeven we slechts mogelijke factoren te onderzoeken. Wanneer we een factor vinden, delen we die volledig uit het getal, zodat het resterende getal en de te onderzoeken grens steeds kleiner worden.

Gekozen programmeeraanpak

We verwijderen eerst alle factoren 2. Het getal 2 is de enige even priemfactor. Zodra alle factoren 2 verdwenen zijn, is het resterende getal oneven en hoeven we geen enkel ander even getal meer te testen.

Daarna onderzoekt een for-lus alleen 3, 5, 7, 9, enzovoort. We beginnen bij 3 omdat dit de kleinste oneven priemfactor is. De stapgrootte 2 zorgt ervoor dat de even kandidaten worden overgeslagen. Iedere gevonden factor wordt zo vaak mogelijk uit het resterende getal gedeeld, want een priemfactor kan meer dan eenmaal voorkomen.

Het is voldoende om mogelijke delers tot de vierkantswortel te testen. Als een getal samengesteld is, heeft het namelijk minstens één factor die niet groter is dan zijn vierkantswortel. We gebruiken isqrt uit de module math om deze gehele vierkantswortel exact te berekenen.

Een range legt zijn bovengrens vast wanneer de for-lus begint, maar resterend_getal wordt tijdens de factorisatie kleiner. Het programma gebruikt daarom eerst een veilige vaste bovengrens en controleert binnen de lus ook de vierkantswortel van de actuele restwaarde. Zo blijft de aanpak correct en kan de lus toch vroegtijdig stoppen.

Na de lus kan nog een getal groter dan 1 overblijven. Dat getal is dan zelf priem; anders hadden we eerder nog een kleinere factor gevonden. Het is bovendien de grootste priemfactor.

Wat betekent `//=`?

De instructie

resterend_getal //= 2

betekent hetzelfde als

resterend_getal = resterend_getal // 2

De operator // is een gehele deling. We gebruiken hem pas nadat we gecontroleerd hebben dat de deler zonder rest in het getal past.

Algoritme

Stel het resterende getal gelijk aan 600851475143.
Deel factor 2 volledig uit.
Test daarna uitsluitend oneven delers vanaf 3.
Deel elke gevonden factor volledig uit en bewaar hem.
Stop zodra het kwadraat van de deler groter is dan het resterende getal.
Gebruik een eventueel resterend getal groter dan 1 als grootste priemfactor.
Druk het antwoord en de uitvoeringstijd af.

Python-programma

import time
from math import isqrt


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


# Zoek de grootste priemfactor met proefdeling
getal = 600_851_475_143
resterend_getal = getal
grootste_priemfactor = 1

# Verwijder eerst alle factoren 2.
# Het getal 2 is de enige even priemfactor. Zolang het resterende getal
# deelbaar is door 2, delen we die factor weg. Na deze stap is het
# resterende getal oneven en hoeven we alleen nog oneven factoren te testen.
while resterend_getal % 2 == 0:
    grootste_priemfactor = 2
    # Dit is een verkorte schrijfwijze voor:
    # resterend_getal = resterend_getal // 2
    # De operator // voert een gehele deling uit.
    resterend_getal //= 2

# Onderzoek de oneven mogelijke priemfactoren
# We beginnen bij 3, het kleinste oneven priemgetal. De stapgrootte 2
# geeft vervolgens 3, 5, 7, 9, ... . Even getallen hoeven niet meer
# getest te worden, want alle factoren 2 zijn al verwijderd.
#
# De bovengrens van range wordt bij het begin van de for-lus vastgelegd.
# Daarom gebruiken we eerst de veilige grens van het huidige restgetal.
vaste_bovengrens = isqrt(resterend_getal)

for deler in range(3, vaste_bovengrens + 1, 2):
    # Het restgetal wordt tijdens de factorisatie kleiner. Met isqrt
    # controleren we daarom ook de actuele vierkantswortel. Zodra de deler
    # daarboven ligt, kan het restgetal geen kleinere factor meer hebben.
    if deler > isqrt(resterend_getal):
        break

    # Deel een gevonden factor volledig weg zolang hij nogmaals voorkomt.
    while resterend_getal % deler == 0:
        grootste_priemfactor = deler
        resterend_getal //= deler

# Na de lus kan het restgetal zelf nog een priemfactor zijn.
if resterend_getal > 1:
    grootste_priemfactor = resterend_getal


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


# Toon het resultaat
print(f"De grootste priemfactor is: {grootste_priemfactor}")
print(f"Uitvoeringstijd: {uitvoeringstijd:.8f} seconden")

Wiskundige achtergrond

Volgens de hoofdstelling van de rekenkunde kan ieder natuurlijk getal $n>1$ , op de volgorde van de factoren na, op unieke wijze geschreven worden als een product van priemgetallen:

$n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}.$

Project Euler 003 komt dus neer op het bepalen van de priemfactorontbinding van $600851475143$ en vervolgens het kiezen van de grootste priemfactor.

Controle met wiskundige software

Ter controle kan de volledige priemfactorontbinding met factorint uit SymPy worden bepaald:

from sympy import factorint

factorisatie = factorint(600851475143)
print(factorisatie)

SymPy geeft als uitvoer:

{71: 1, 839: 1, 1471: 1, 6857: 1}

In gewone wiskundige notatie is dit

$600851475143=71\cdot839\cdot1471\cdot6857.$

SymPy wordt hier alleen gebruikt als onafhankelijke controle van de factorisatie. Deze controle vervangt de eigen Python-oplossing niet.

Resultaat

De grootste priemfactor van 600851475143 is 6857.

Uitvoeringstijd: ongeveer 0,00018511 seconden.

Besluit

Proefdeling is voor deze opgave eenvoudig, inzichtelijk en snel genoeg. Door gevonden factoren meteen volledig uit te delen, blijft het aantal benodigde controles beperkt en vinden we zonder externe bibliotheken het juiste antwoord.