Despre ciurul lui Eratostene - cel mai vechi ciur pentru numere prime
Ciurul lui Eratostene găsește toate numerele prime până la o limită fără nicio împărțire. Doar numărați: tăiați fiecare al doilea număr după 2, fiecare al treilea după 3 și așa mai departe. Ce rămâne sunt numerele prime. După mai bine de două mii de ani, este încă una dintre cele mai rapide metode de a le enumera.
Eratostene din Cirene
Eratostene a trăit aproximativ între 276 și 194 î.Hr. și a condus marea bibliotecă din Alexandria. Este cunoscut mai ales pentru că a măsurat mărimea Pământului din lungimea umbrelor în două orașe. Ciurul îi poartă numele pentru că Nicomah din Gerasa l-a descris drept metoda lui în Introducere în aritmetică, scrisă în jurul anului 100 d.Hr.
Cum funcționează ciurul
Scrieți numerele de la 2 la N. Primul număr, 2, este prim: tăiați 4, 6, 8 și fiecare alt multiplu al lui 2. Următorul număr rămas, 3, este prim: tăiați 9, 12, 15 și așa mai departe. Continuați cu 5, 7 și următoarele numere rămase. Un număr care nu este tăiat niciodată nu are niciun factor mai mic, deci este prim.
Oprirea la rădăcina pătrată
Fiecare număr compus până la N are un factor prim care nu este mai mare decât rădăcina pătrată din N. Deci, imediat ce p² depășește N, nu mai este nimic de tăiat. Pentru numerele prime până la 100 aveți nevoie doar de 2, 3, 5 și 7, iar pentru 1000 de numerele prime până la 31.
Cât de rapid este?
Ciurul are nevoie de aproximativ N log log N pași, ceea ce crește doar puțin mai repede decât N însuși. Calculatoarele îl folosesc încă, adesea pe bucăți, ca ciur segmentat, pentru a enumera numere prime până la miliarde. Pentru a testa dacă un singur număr mare este prim, alte metode sunt mai rapide.
Întrebări frecvente
Cine a inventat ciurul lui Eratostene?
Poartă numele lui Eratostene din Cirene, un învățat grec din secolul al III-lea î.Hr. Cea mai veche descriere scrisă îi aparține lui Nicomah din Gerasa, în jurul anului 100 d.Hr.
De ce începe ciurul să taie de la p²?
Fiecare multiplu mai mic al lui p are un factor prim mai mic, deci un număr prim mai mic l-a tăiat deja.
Câte numere prime sunt sub 1000?
Sunt 168 de numere prime sub 1000. Cel mai mare este 997.
Unelte conexe
Ciurul lui Eratostene
Urmăriți cum ciurul lui Eratostene găsește numerele prime până la 100, 200, 500 sau 1000. Fiecare număr prim își taie multiplii în propria culoare, pas cu pas.
Spirala lui Ulam
Desenează spirala lui Ulam în browser. Marchează numerele prime, citește polinomul de gradul al doilea de pe fiecare diagonală și deschide șirul neîntrerupt de 40 de numere prime al lui Euler.
Spirala lui Ulam
Cum așază spirala lui Stanisław Ulam din 1963 numerele întregi pe o grilă pătrată, de ce se adună numerele prime pe diagonale pătratice și unde stau cele patruzeci de numere prime ale lui Euler când spirala pornește de la 41.
Conjectura Collatz
Explorează problema Collatz 3n+1 în browser. Urmărește șiruri grindină, crește un arbore Collatz geometric și mărește fractalul Collatz continuu.
Eşti gata să încerci?
Deschide PictorX în browser-ul tău
Încercați ciurul lui Eratostene