Ciurul lui Eratostene
Câte numere prime există? La această întrebare a fost găsit răspunsul încă din antichitate, de către Euclid. Acesta a afirmat că există o infinitate de numere prime. Dar cum demonstrăm că acesta este adevărul?
Să presupunem că există un număr finit de numere prime. Vom nota mulţimea numerelor prime
P = {p1, p2, p3, ..., pn}.
Notăm produsul numerelor din mulţimea numerelor prime P cu a
a = p1 * p2 * p3 * ... * pn
Acum vom construi numărul
g = a + 1.
Este evident că numărul g nu este divizibil cu niciun număr prim (pentru că g şi a sunt numere consecutive, iar numerele consecutive sunt prime între ele - adică nu au decât un singur divizor comun, respectiv numărul 1), ceea ce înseamnă că g este un număr prim (orice număr compus poate fi scris ca un produs de mai multe numere prime care îl divid).
Întrucât g este un număr prim, îl adăugăm la mulţimea numerelor prime, iar apoi repetăm procedeul.
Observăm că acest procedeu va fi repetat la infinit, deci, în concluzie, şi mulţimea numerelor prime este infinită.
###
CIURUL LUI ERATOSTENE
În imaginea de mai sus este ceea ce se numeşte Ciurul lui Eratostene.
În matematică, ciurul lui Eratostene este un algoritm simplu și vechi de descoperire a tuturor numerelor prime până la un întreg specificat. Este predecesorul algoritmului modern ciurul lui Atkin, un algoritm mai rapid, dar mai complex. A fost creat de Eratostene, un matematician din Grecia antică.
Algoritm este următorul.
1. Se scrie o listă a numerelor de la 2 la cel mai mare număr ce urmează a fi testat pentru primalitate. Numim această listă lista A. (Lista de pătrate din partea stângă a imaginii.)
2. Se trece numărul 2, primul număr prim găsit, într-o altă listă, cea a numerelor prime găsite. Numim această listă lista B. (Este lista din partea dreaptă a imaginii.)
3. Se marchează 2 și toți multiplii lui 2 din lista A.
4. Primul număr nemarcat din listă este un număr prim. Se trece acest număr în lista B.
5. Se marchează acest număr și toți multiplii lui din lista A. Marcarea de multipli poate să înceapă de la pătratul numărului, întrucât multiplii mai mici au fost deja marcați în pașii anteriori.
5. Se repetă pașii 4 și 5 până când se epuizează toate numerele din lista A.
Sursa informaţiei pentru ciurul lui Eratostene: wikipedia.org
