Primalitetstest upp till sqrt(n)
Kontrollera ett enda tal effektivt
Primalitetstest upp till sqrt(n) är en gratis lektion i Competitive Programming Academy 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 Competitive Programming Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Competitive Programming Academy 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 Python 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
- 30
- Lektioner
- 120
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 Competitive Programming Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Primalitetstest upp till sqrt(n)”?
Kontrollera ett enda tal effektivt Ni övar på Competitive Programming Academy 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 Competitive Programming Academy?
Du behöver inga förkunskaper. Utbildningen i Competitive Programming Academy 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 Competitive Programming Academy-lektionen?
Ja. Varje Competitive Programming Academy-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