Priemfactorisatie en delers
N opsplitsen in priemmachten en delers tellen
Priemfactorisatie en delers is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Ontbind N
Elk gehele getal groter dan 1 is een uniek product van priemgetallen. Het vinden van die ontbinding, de priemfactorisatie, maakt veel problemen uit de getaltheorie toegankelijk. 🧩
Het idee achter proefdeling
Haal de kleinste priemfactor die n deelt eruit, deel die weg en herhaal. Met deze eenvoudige proefdeling breng je n terug tot 1.
Loop tot de wortel
Test delers i zolang i*i kleiner dan of gelijk aan n blijft. Na de vierkantswortel kan er nog hoogstens één priemfactor overblijven.
while i * i <= n:
...Haal elke factor eruit
Zolang i n deelt, blijf je delen en leg je i vast. Zo leg je de volledige macht van die priem vast voordat je verdergaat.
while n % i == 0:
factors.append(i)
n //= iDe overgebleven priemfactor
Als n na de lus nog groter dan 1 is, is n zelf een priemfactor die groter is dan de vierkantswortel. Voeg die één keer toe.
if n > 1:
factors.append(n)De volledige routine
Samen levert dit factorisatie in O(sqrt n)-tijd op, waarbij elke priem met zijn volledige multipliciteit in volgorde wordt teruggegeven.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return fGroepeer in machten
Voor het tellen van delers wil je elke priem met zijn exponent, zoals 2^3 in plaats van 2,2,2. Een Counter telt de herhalingen netjes.
from collections import Counter
exp = Counter(factorize(n))De formule voor delers
Als n p1^a maal p2^b is, is het aantal delers (a+1) maal (b+1). Elke exponent krijgt één extra keuze.
Delers tellen
Vermenigvuldig voor alle priemgetallen de exponenten plus één met elkaar. Zo krijg je het totale aantal delers zonder ze allemaal op te sommen.
count = 1
for e in exp.values():
count *= (e + 1)Delers optellen
Met een verwante formule tel je delers op met de meetkundige reeks van elk priemgetal. Als je dit kent, helpt het bij problemen met perfecte getallen en aliquote rijen.
Snelheid met een zeef
Bereken bij veel ontbindingen vooraf de kleinste priemfactor van elk getal met een zeef. Daarna ontbindt elke opvraag in log n stappen.
Korte controle
Pas de formule voor het tellen van delers toe op een concreet getal.
Samenvatting
Je kunt N nu door proefdeling ontbinden in O(sqrt n), de overgebleven priemfactor meenemen, exponenten groeperen en delers tellen met de productformule. ✅
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Priemfactorisatie en delers” gratis?
Ja — de volledige tekst van “Priemfactorisatie en delers” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Priemfactorisatie en delers”?
N opsplitsen in priemmachten en delers tellen Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Priemfactorisatie en delers”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- GCD, LCM en het algoritme van Euclides
- Primaliteit testen tot sqrt(n)
- Zeef van Eratosthenes
- Priemfactorisatie en delers