Primtalsfaktorisering och delare
Dela upp N i primtalspotenser och räkna delare
Primtalsfaktorisering och delare är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Dela upp N
Varje heltal större än 1 är en unik produkt av primtal. Att hitta denna uppdelning, dess primtalsfaktorisering, löser många problem inom talteori. 🧩
Idén med prövande division
Ta ut det minsta primtalet som delar n, dividera bort det och upprepa. Denna enkla prövande division bryter ner n till 1.
Loopa till roten
Testa delare i så länge i*i är högst n. Efter kvadratroten kan högst en primtalsfaktor återstå.
while i * i <= n:
...Extrahera varje faktor
Så länge i delar n fortsätter du att dividera och registrerar i. På så sätt fångar du hela potensen av det primtalet innan du går vidare.
while n % i == 0:
factors.append(i)
n //= iDet återstående primtalet
Efter loopen är n, om det fortfarande är större än 1, självt en primtalsfaktor som är större än kvadratroten. Lägg till det en gång.
if n > 1:
factors.append(n)Hela rutinen
Tillsammans ger detta en faktorisering på O(sqrt n)-tid, där varje primtal returneras med sin fulla multiplicitet i rätt ordning.
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 fGruppera i potenser
För att räkna delare vill du ha varje primtal tillsammans med sin exponent, till exempel 2^3 i stället för 2,2,2. En Counter räknar upprepningarna på ett enkelt sätt.
from collections import Counter
exp = Counter(factorize(n))Formeln för antal delare
Om n är p1^a gånger p2^b är antalet delare (a+1) gånger (b+1). Varje exponent ger ett extra val.
Räkna antalet delare
Multiplicera ihop ett plus varje exponent för alla primtal. Då får Du det totala antalet delare utan att behöva räkna upp dem.
count = 1
for e in exp.values():
count *= (e + 1)Summa av delare
En närliggande formel summerar delarna med hjälp av varje primtals geometriska serie. Om Du kan den blir problem med perfekta tal och aliquotproblem enklare.
Snabbhet med ett såll
För många faktoriseringar kan Du förberäkna varje tals minsta primtalsfaktor med ett såll. Därefter kan varje fråga faktoriseras på log n steg.
Snabb kontroll
Använd formeln för att räkna antalet delare på ett konkret tal.
Sammanfattning
Du kan nu faktorisera N med provdivision på O(sqrt n), hantera det kvarvarande primtalet, gruppera exponenterna och räkna delarna med produktformeln. ✅
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Primtalsfaktorisering och delare” gratis?
Ja – hela texten till ”Primtalsfaktorisering och delare” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Primtalsfaktorisering och delare”?
Dela upp N i primtalspotenser och räkna delare Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Primtalsfaktorisering och delare”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- GCD, LCM och Euklides algoritm
- Primalitetstest upp till sqrt(n)
- Eratosthenes såll
- Primtalsfaktorisering och delare