GCD, LCM en het algoritme van Euclides
Delers snel en correct berekenen
GCD, LCM en het algoritme van Euclides is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 1 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.
Waarom delers belangrijk zijn
Zoveel wedstrijdopgaven draaien om gemeenschappelijke factoren van twee getallen. Het belangrijkste hulpmiddel hiervoor is de ggd, de grootste gemene deler. 🔢
Wat ggd betekent
De ggd van twee gehele getallen is het grootste getal dat beide zonder rest deelt. Voor 12 en 18 is dat 6, want 6 deelt beide precies.
De trage aanpak
Je zou elk getal vanaf de kleinere waarde naar beneden kunnen controleren tot je een getal vindt dat beide deelt. Dat werkt, maar is veel te traag voor grote invoer.
Het inzicht van Euclides
Het algoritme van Euclides is de snelle aanpak. Het kernidee: de ggd van a en b is gelijk aan de ggd van b en de rest van a gedeeld door b.
De herhalingsregel
Herhaal de stap waarbij je de waarden verwisselt en de rest neemt totdat de rest nul wordt. De laatste waarde die niet nul is, is je antwoord: de ggd zelf.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aSchrijf de code zelf
Een korte lus vervangt het paar steeds opnieuw totdat b nul wordt. Dit gaat in ongeveer log stappen en is zelfs voor enorme getallen razendsnel.
def gcd(a, b):
while b:
a, b = b, a % b
return aGebruik de standaardbibliotheek
Je hoeft dit zelden zelf te schrijven. Python bevat math.gcd, dat correct en snel is en argumenten met nul voor je afhandelt.
from math import gcd
print(gcd(12, 18))Van ggd naar kgv
Het kgv, het kleinste gemene veelvoud, is het kleinste getal dat door beide waarden deelbaar is. Het hangt rechtstreeks samen met de ggd die je net hebt berekend.
De formule voor het kgv
Vermenigvuldig de twee getallen en deel het resultaat daarna door hun ggd. Deel altijd eerst om overloop bij zeer grote producten te voorkomen.
def lcm(a, b):
return a // gcd(a, b) * bGgd van een hele lijst
Om de ggd over veel getallen te berekenen, koppel je ze paarsgewijs. Python's reduce past math.gcd van links naar rechts toe op de lijst.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Verwerk het geval met nul
Volgens de definitie is gcd(a, 0) gelijk aan a en is gcd(0, 0) gelijk aan 0. Als je dit randgeval kent, blijven je lussen ook bij lege invoer correct werken.
Snelle controle
Tijd om de kernstap van Euclides te bevestigen.
Samenvatting
Je kunt nu de ggd met het algoritme van Euclides in logaritmische tijd berekenen, daaruit het kgv afleiden en beide stapsgewijs op een lijst toepassen. ✅
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 “GCD, LCM en het algoritme van Euclides” gratis?
Ja — de volledige tekst van “GCD, LCM en het algoritme van Euclides” 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 “GCD, LCM en het algoritme van Euclides”?
Delers snel en correct berekenen 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 1 van 4.
Hoe lang duurt de les “GCD, LCM en het algoritme van Euclides”?
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