Ciurul lui Eratostene

Acum îți voi prezenta o metodă antică pentru a genera o listă de numere prime până la o limită N, metodă numită Ciurul lui Eratostene. Eratostene s-a născut în 276 î.e.n. Deci, această metodă e veche de 2200 de ani. Dar este foarte simplă și elegantă și o poți prezenta oricărui copil. Să zicem că vrem să calculăm toate numerele prime până la 100, S-ar proceda exact la fel dacă am vrea să calculăm până la 10 000 sau un miliard. Uite cum facem: presupunem că toate numerele sunt nemarcate (gri înseamnă nemarcat). Începem de la doi: dacă găsim un număr care e nemarcat, vom ști că e prim. Îl avem pe doi: doi este prim deoarece nu e marcat. În a doua etapă eliminăm toți multiplii lui doi: știm că reprezintă numere compuse. Bum, parcurgem numerele și eliminăm toți multiplii lui doi; roșu înseamnă compus. Iar acum repetăm. Trecem de la doi la trei. Trei este nemarcat așa că vom marca trei ca fiind prim. Iar acum putem elimina toți multiplii lui trei. Putem să facem mai rapid: - observă că șase este deja tăiat - vom marca de fapt toți multiplii începând de la pătratul perfect al acelui număr. Așadar trei înmulțit cu trei este nouă. Începem de la nouă și marcăm toți multiplii lui trei ca fiind compuși. Iar apoi ne întoarcem și sărim la patru. Patru e deja marcat, știm că este prim. Trecem la cinci, și găsim un alt număr nemarcat, cinci, care este prim. Acum, de cinci ori cinci dă 25, vom sări la 25. Marcăm 25, 30, 35, 40, 45, și așa mai departe. Acestea sunt numere compuse. Mergem înainte până ajungem la șapte, știm că șapte este prim deoarece nu este marcat. Șapte înmulțit cu șapte este 49, marcăm 49 iar apoi marcăm toți multiplii lui 7 de după 49 ca fiind compuși. Revenim și ajungem la 11, 11 este prim. Observă că 11 înmulțit cu 11 dă un număr mai mare decât 100, deci ne putem opri în acest punct. Ne-am fi putut opri la 10 chiar, deoarece acum toate numerele rămase nemarcate, după cum se vede, sunt prime. Iar, cu o singură mișcare, le marcăm pe toate ca fiind prime. Iar acesta e întregul algoritm, e atât de simplu. Acum, să generalizăm ce am făcut, pentru a scrie un program care să treacă numerele prin ciur. Dacă vrem să găsim toate numerele prime până la un număr N, trebuie întâi să creăm o buclă principală. Deci avem pentru toate numerele A, de la 2 până la rădăcina pătrată a lui N. Remarcă, aici ne-am oprit când am ajuns la 10. Am arătat la 11, ne oprim fiindcă am găsit toate numerele prime. Deci de la 2 până la rădăcina pătrată a lui N, procedăm așa: dacă A e nemarcat, atunci știm că A e prim, iar când găsim un număr prim marcăm toți multiplii lui A ca fiind numere compuse. Asta e tot! Deci, găsești un număr prim, îi marchezi multiplii, te întorci la început, incrementezi A cu unu. Deci suntem la doi și trecem la trei apoi la patru, cinci și așa mai departe, iar când terminăm, am aflat toate numerele prime. Vezi aici că și aceasta este o buclă. Avem o buclă principală pentru când găsim un număr prim. Iar această marcare a multiplilor e și ea la rândul ei o buclă. E important de văzut aici că avem o buclă imbricată, avem o buclă în interiorul alteia. Aici e un exemplu în acțiune al acestui algoritm, l-am scris aici în JavaScript. Dacă pun 100, vedem aici toate numerele prime sub 100. Dacă pun 200, avem aici toate numerele prime sub 200. Iar dacă pun 850, vedem aici toate numerele prime sub 850. Astfel avem acest program cu o înregistrare care explică cum l-am creat.