Primfaktorisering og divisorer
Opdel N i primtalspotensser, og tæl divisorer
Primfaktorisering og divisorer er en gratis Competitive Programming Academy-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Competitive Programming Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Opdel N
Ethvert heltal større end 1 er et entydigt produkt af primtal. Ved at finde denne opdeling, altså dets primtalsfaktorisering, kan du løse mange talteoretiske problemer. 🧩
Idéen bag prøvedivision
Træk det mindste primtal, der går op i n, ud, dividér det væk, og gentag. Denne enkle prøvedivision reducerer n til 1.
Løkke til kvadratroden
Test divisorer i, så længe i*i er mindre end eller lig med n. Efter kvadratroden kan der højst være én primfaktor tilbage.
while i * i <= n:
...Udtræk hver faktor
Så længe i går op i n, fortsætter du med at dividere og registrerer i. Det fanger den fulde potens af primtallet, før du går videre.
while n % i == 0:
factors.append(i)
n //= iDet resterende primtal
Hvis n stadig er større end 1 efter løkken, er n selv en primfaktor, der er større end kvadratroden. Tilføj den én gang.
if n > 1:
factors.append(n)Hele rutinen
Samlet giver dette en faktorisering på O(sqrt n)-tid, der returnerer hvert primtal med sin fulde multiplicitet i rækkefø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
Hvis du vil tælle divisorer, skal du have hvert primtal sammen med dets eksponent, for eksempel 2^3 i stedet for 2,2,2. En Counter tæller gentagelserne på en enkel måde.
from collections import Counter
exp = Counter(factorize(n))Divisorformlen
Hvis n er p1^a gange p2^b, er antallet af divisorer (a+1) gange (b+1). Hver eksponent giver ét ekstra valg.
Tæl divisorer
Gang én plus hver eksponent for hvert primtal sammen. Det giver det samlede antal divisorer uden at opliste dem.
count = 1
for e in exp.values():
count *= (e + 1)Sum af divisorer
En beslægtet formel summerer divisorer ved hjælp af den geometriske række for hvert primtal. Det er nyttigt i problemer om perfekte tal og aliquotfølger.
Hurtigere med et si
Ved mange faktoriseringer kan du på forhånd beregne hvert tals mindste primfaktor med et si. Derefter kan hver forespørgsel faktoriseres på log n trin.
Hurtigt tjek
Anvend formlen til at tælle divisorer på et konkret tal.
Opsummering
Du kan nu faktorisere N med prøvevis division i O(sqrt n), håndtere den resterende primfaktor, gruppere eksponenter og tælle divisorer med produktformlen. ✅
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Primfaktorisering og divisorer” gratis?
Ja — hele teksten til “Primfaktorisering og divisorer” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Competitive Programming Academy-kurset, skal du opgradere til CoddyKit PRO. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Primfaktorisering og divisorer”?
Opdel N i primtalspotensser, og tæl divisorer Du øver dig i Competitive Programming Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Competitive Programming Academy?
Der kræves ingen tidligere erfaring. Competitive Programming Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Primfaktorisering og divisorer”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Competitive Programming Academy-lektion?
Ja. Alle Competitive Programming Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- GCD, LCM og den euklidiske algoritme
- Primtalstest op til sqrt(n)
- Eratosthenes' si
- Primfaktorisering og divisorer