Probabil că vă mai amintiţi din şcoală (iar dacă sunteţi în această etapă a vieţii şi nu aţi învăţat încă, veţi afla acum) despre ciurul lui Eratostene, cea mai veche modalitate cunoscută de determinare a tuturor numerelor prime mai mici decât un număr natural dat, fie acesta n. Algoritmul este unul de-a dreptul banal, ba poate chiar plicticos. Se scriu, pe hârtie, pe tablă, ori, de ce nu, prin intermediul unui program de calculator, în memoria acestuia, numerele naturale cuprinse între 2 (cel mai mic număr prim) şi numărul dat n. Apoi se elimină succesiv, în ordine crescătoare, multiplii fiecărui număr natural rămas în listă, plecând de la 2. Când ne oprim ? Când nu mai este nimic de eliminat, ori când programul de computer implementat ne anunţă că am eliminat toate numerele ne-prime din listă.
Ciurul lui Eratostene pentru n=120
Credit: wikimedia.org
Dacă accesaţi acest link de pe pagina Universităţii din Chicago a Statului Illinois, veţi putea vedea ciurul lui Eratostene la lucru folosind doar câteva clicuri de mouse.