Primtalstest op til sqrt(n)
Kontrollér et enkelt tal effektivt
Primtalstest op til sqrt(n) er en gratis Competitive Programming Academy-lektion på CoddyKit. Dette er lektion 2 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.
Spørgsmålet om primtal
En grundlæggende færdighed i matematik er at afgøre, om et enkelt tal er et primtal. Et primtal har præcis to divisorer: 1 og sig selv. Lad os teste det hurtigt. 🔍
Den naive kontrol
Du kunne forsøge at dividere n med hvert tal fra 2 til n minus 1. Det er korrekt, men smerteligt langsomt, når n er stort.
Tricket med kvadratroden
Her er den centrale indsigt: Du behøver kun teste divisorer op til kvadratroden af n. Derefter kan der ikke dukke nogen ny faktor op.
Hvorfor kvadratroden er nok
Divisorer kommer i par, hvis produkt er n. Hvis begge var større end kvadratroden, ville deres produkt være større end n, hvilket er umuligt.
Løkkens grænse
Gå gennem i fra 2, så længe i gange i er mindre end eller lig med n. Ved at bruge i*i undgår du afrundingsfejl fra sqrt for store heltal.
while i * i <= n:
...Håndtér små tilfælde
Tal under 2 er aldrig primtal, så afvis dem med det samme. Denne kontrol holder din hovedløkke enkel og korrekt.
if n < 2:
return FalseHele funktionen
Saml det hele: Kontrollér små værdier, og gennemgå derefter mulige divisorer op til kvadratroden. Hvis divisionen går op, er n sammensat.
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 hurtigere
Kontrollér 2 særskilt, og test derefter kun ulige tal. Når du springer lige tal over, halverer du omtrent arbejdet uden ekstra kompleksitet.
if n % 2 == 0:
return n == 2Tidsforbruget
Denne test kører på O(sqrt n)-tid. For ét tal på op til en milliard er det kun omkring 30.000 billige operationer.
Ét tal, ikke mange
sqrt-testen er bedst til én eller få forespørgsler. Hvis du skal teste primtal for et helt interval, er en si meget hurtigere.
Undgå fejlen med sqrt
Ved at sammenligne med i*i i stedet for math.sqrt undgår du afrundingsfejl, som ellers kan få dig til fejlagtigt at acceptere eller afvise tal tæt på grænsen.
Hurtigt tjek
Bekræft grænsen, der gør denne test hurtig.
Opsummering
Du kan nu teste, om ét tal er et primtal, på O(sqrt n)-tid, kontrollere små værdier, springe lige tal over og bruge i*i for at bevare den nøjagtige beregning. ✅
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 “Primtalstest op til sqrt(n)” gratis?
Ja — hele teksten til “Primtalstest op til sqrt(n)” 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 “Primtalstest op til sqrt(n)”?
Kontrollér et enkelt tal effektivt 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 2 af 4.
Hvor lang tid tager lektionen “Primtalstest op til sqrt(n)”?
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