Eratosthenes' si
List alle primtal op til N på næsten lineær tid
Eratosthenes' si er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 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 Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Primtal i større mængder
Nogle gange har du brug for alle primtal op til N, ikke kun én kontrol. Eratosthenes' si finder dem alle i én gennemgang. 🧹
Hovedideen
Begynd med at antage, at alle tal er primtal. Kryds derefter multipla af hvert primtal, du finder, ud, så kun de ægte primtal bliver tilbage.
Opret markeringerne
Opret en boolesk liste, hvor indeks i angiver, om i er et primtal. Dette array er det lærred, sien arbejder på.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseGå kandidaterne igennem
Gå op gennem i. Første gang du når et tal, der stadig er markeret True, må det være et nyt primtal uden en mindre faktor.
Kryds multipla ud
For hvert primtal i markeres 2i, 3i, 4i og så videre som ikke-primtal. Disse multipla har tydeligvis i som divisor.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseStart ved i*i
Begynd med at krydse ud ved i*i, ikke ved 2i. Alle mindre multipla er allerede fjernet af et tidligere primtal, så du kan springe dem over.
Stop ved kvadratroden
Du behøver kun bruge sien, så længe i*i er mindre end eller lig med N. Efter kvadratroden er alle resterende True-markeringer allerede primtal.
Hele sien
Kombinér den ydre gennemgang med den indre udkrydsning. Efter løkken er hvert indeks, der stadig er markeret True, et bekræftet primtal.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseSaml primtallene
Læs de færdige markeringer ind i en liste med en list comprehension. Nu har du alle primtal op til N klar til hurtige forespørgsler.
primes = [i for i, p in enumerate(is_prime) if p]Hvorfor det er hurtigt
Sien kører på omkring O(n log log n)-tid, altså næsten lineært. Derfor er den langt hurtigere end gentagne test af enkeltstående tal.
Vær opmærksom på hukommelsen
Markeringstabellen bruger hukommelse proportionalt med N. Ved meget store grænser skal du overveje dit pladsforbrug, før du allokerer.
Hurtigt tjek
Husk den lille optimering i den indre løkke.
Opsummering
Du kan nu bygge en si, der oplister alle primtal op til N på næsten lineær tid, starter hvert primtal ved i*i og stopper ved kvadratroden. ✅
Lær Forberedelse til kodeinterviews 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
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Eratosthenes' si” gratis?
Ja — hele teksten til “Eratosthenes' si” 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 Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Eratosthenes' si”?
List alle primtal op til N på næsten lineær tid Du øver dig i Forberedelse til kodeinterviews 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å Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews 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 3 af 4.
Hvor lang tid tager lektionen “Eratosthenes' si”?
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 Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-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