Primalitetstest upp till sqrt(n)
Kontrollera ett enda tal effektivt
Primalitetstest upp till sqrt(n) är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 2 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.
Frågan om primtal
En grundläggande matematisk färdighet är att avgöra om ett enskilt tal är ett primtal. Ett primtal har exakt två delare: ett och sig självt. Låt oss testa det snabbt. 🔍
Den naiva kontrollen
Du kan försöka dividera n med varje tal från 2 till n minus 1. Det är korrekt, men plågsamt långsamt när n är stort.
Kvadratrots-tricket
Här är den viktiga insikten: du behöver bara testa delare upp till kvadratroten ur n. Efter den punkten kan ingen ny faktor dyka upp.
Varför kvadratroten räcker
Delare kommer i par vars produkt är n. Om båda låg över kvadratroten skulle deras produkt överstiga n, vilket är omöjligt.
Loopens gräns
Iterera i från 2 så länge i gånger i är högst n. Genom att använda i*i undviker du flyttalsfel från sqrt för stora heltal.
while i * i <= n:
...Hantera små fall
Tal mindre än 2 är aldrig primtal, så avvisa dem direkt. Detta skydd håller huvudloopen ren och korrekt.
if n < 2:
return FalseHela funktionen
Sätt ihop allt: hantera små värden först och gå sedan igenom möjliga delare upp till roten. Om divisionen går jämnt är n sammansatt.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TrueGör den snabbare
Kontrollera 2 separat och testa sedan endast udda tal. Genom att hoppa över jämna tal halverar du ungefär arbetet utan extra komplexitet.
if n % 2 == 0:
return n == 2Tidskostnaden
Detta test körs på O(sqrt n)-tid. För ett enskilt tal upp till en miljard innebär det bara omkring 30 000 enkla operationer.
Ett tal, inte många
Kvadratrots-testet är utmärkt för en eller några få frågor. Om du behöver testa primtal för ett helt intervall är ett såll mycket snabbare.
Undvik kvadratrotsfällan
Genom att jämföra med i*i i stället för math.sqrt undviker du avrundningsfel som annars felaktigt kan godkänna eller underkänna tal nära gränsen.
Snabb kontroll
Bekräfta gränsen som gör detta test snabbt.
Sammanfattning
Nu kan du testa om ett tal är ett primtal på O(sqrt n)-tid, hantera små värden, hoppa över jämna tal och använda i*i för exakta resultat. ✅
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 ”Primalitetstest upp till sqrt(n)” gratis?
Ja – hela texten till ”Primalitetstest upp till sqrt(n)” 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 ”Primalitetstest upp till sqrt(n)”?
Kontrollera ett enda tal effektivt 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 2 av 4.
Hur lång tid tar lektionen ”Primalitetstest upp till sqrt(n)”?
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