GCD, LCM og den euklidske algoritmen
Beregn divisorer raskt og korrekt
GCD, LCM og den euklidske algoritmen er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hvorfor divisorer er viktige
Så mange konkurranseoppgaver avhenger av felles faktorer i to tall. Det aller nyttigste verktøyet her er GCD, den største felles divisoren. 🔢
Hva GCD betyr
GCD for to heltall er det største tallet som deler begge uten rest. For 12 og 18 er den 6, siden 6 deler begge helt opp.
Den langsomme metoden
De kan teste alle tall fra den minste verdien og nedover til De finner et tall som deler begge. Det fungerer, men er altfor langsomt for store inndata.
Den euklidske innsikten
Euklids algoritme er den raske metoden. Hovedideen er at GCD-en til a og b er lik GCD-en til b og resten når a deles på b.
Rekursjonen
Gjenta bytte- og modulo-trinnet til resten blir null. Den siste gjenværende verdien som ikke er null, er svaret, altså selve GCD-en.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aSkriv koden selv
En kort løkke erstatter paret om og om igjen til b blir null. Dette bruker omtrent log-trinn og går lynraskt selv for enorme tall.
def gcd(a, b):
while b:
a, b = b, a % b
return aBruk standardbiblioteket
De trenger sjelden å implementere dette selv. Python har math.gcd, som er korrekt og rask, og som håndterer nullargumenter for Dem.
from math import gcd
print(gcd(12, 18))Fra GCD til LCM
LCM, det minste felles multiplumet, er det minste tallet som begge verdiene deler. Det henger direkte sammen med GCD-en De nettopp beregnet.
LCM-formelen
Multipliser de to tallene og divider deretter med GCD-en deres. Divider alltid først én av faktorene med GCD-en for å unngå overflow i svært store produkter.
def lcm(a, b):
return a // gcd(a, b) * bGCD for en hel liste
For å beregne GCD-en for mange tall trinnvis kobler De dem sammen parvis. Pythons reduce bruker math.gcd fra venstre mot høyre over listen.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Håndter nulltilfellet
Per definisjon er gcd(a, 0) lik a, og gcd(0, 0) er 0. Når De kjenner dette kanttilfellet, unngår De at løkkene oppfører seg feil ved tom input.
Rask sjekk
På tide å bekrefte det sentrale euklidske trinnet.
Oppsummering
De kan nå beregne GCD med Euklids algoritme på log-trinn, utlede LCM fra den og beregne begge trinnvis over en liste. ✅
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «GCD, LCM og den euklidske algoritmen» gratis?
Ja – hele teksten i «GCD, LCM og den euklidske algoritmen» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «GCD, LCM og den euklidske algoritmen»?
Beregn divisorer raskt og korrekt Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «GCD, LCM og den euklidske algoritmen»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- GCD, LCM og den euklidske algoritmen
- Primtallstesting opptil sqrt(n)
- Eratosthenes' sil
- Primtallsfaktorisering og divisorer