Primtallsfaktorisering og divisorer
Bryt N ned i primtallspotenser og tell divisorer
Primtallsfaktorisering og divisorer er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 4 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 Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Bryt ned N
Hvert heltall større enn 1 er et entydig produkt av primtall. Ved å finne denne nedbrytningen, altså tallets primtallsfaktorisering, kan De løse mange problemer innen tallteori. 🧩
Ideen med prøvedivisjon
Trekk ut det minste primtallet som deler n, del det bort, og gjenta. Denne enkle prøvedivisjonen bryter n ned til 1.
Løkke til roten
Test divisorer i så lenge i*i er mindre enn eller lik n. Etter kvadratroten kan det høyst gjenstå én primtallsfaktor.
while i * i <= n:
...Trekk ut hver faktor
Så lenge i deler n, fortsetter De å dele og registrerer i. Slik fanger De hele potensen til dette primtallet før De går videre.
while n % i == 0:
factors.append(i)
n //= iDet gjenværende primtallet
Etter løkken er n fortsatt større enn 1, er n selv en primtallsfaktor som er større enn kvadratroten. Legg den til én gang.
if n > 1:
factors.append(n)Hele rutinen
Tilsammen gir dette faktorisering på O(sqrt n) tid, og returnerer hvert primtall med full multiplisitet i riktig rekkefølge.
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 fGruppér i potenser
For å telle divisorer trenger De hvert primtall sammen med eksponenten sin, for eksempel 2^3 i stedet for 2,2,2. En Counter teller gjentakelsene på en ryddig måte.
from collections import Counter
exp = Counter(factorize(n))Formelen for divisorer
Hvis n er p1^a ganger p2^b, er antallet divisorer (a+1) ganger (b+1). Hver eksponent gir ett ekstra valg.
Tell divisorer
Multipliser én pluss hver eksponent for alle primtall. Dette gir det totale divisorantallet uten å måtte liste dem opp.
count = 1
for e in exp.values():
count *= (e + 1)Sum av divisorer
En relatert formel summerer divisorer ved hjelp av den geometriske rekken til hvert primtall. Det er nyttig å kjenne den for problemer om perfekte tall og aliquot-problemer.
Få fart med en sil
For mange faktoriseringer kan du forhåndsberegne hvert talls minste primfaktor med en sil. Da kan hver spørring faktoriseres på log n-trinn.
Rask sjekk
Bruk formelen for å telle divisorer på et konkret tall.
Oppsummering
Du kan nå faktorisere N med prøvedivisjon i O(sqrt n), ta vare på den gjenværende primtallsfaktoren, gruppere eksponenter og telle divisorer med produktformelen. ✅
Lær deg Python 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
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Primtallsfaktorisering og divisorer» gratis?
Ja – hele teksten i «Primtallsfaktorisering og divisorer» 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 Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Primtallsfaktorisering og divisorer»?
Bryt N ned i primtallspotenser og tell divisorer Du øver på Competitive Programming Academy 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 Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy 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 4 av 4.
Hvor lang tid tar leksjonen «Primtallsfaktorisering og divisorer»?
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 Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-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