Ciurul lui Eratostene
– numerele prime sunt “caramizile” din care sunt formate numerele naturale
Definitie : un numar p apartine lui N (multimea numerele naturale) se numeste numar prim daca are ca divizor pe 1 si p si numai pe acestea
exemplu : 2 are ca divizor pe 1 si pe 2
D= divizor
D(2) = {1,2} = este prim
D(3) = {1,3} = este prim
D(4) = { 1,2,4} = nu este prim
D(5) = { 1,5} = este prim
Ciurul lui Eratostene = luam un sir de numere pana la 25 si le scriem asa :
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
– ce spune algoritmul ? = luam nr. 2 si taiem toti multipli cu 2, adica : 2,4,6,8,10,12,14,16,18,20,22,24
– apoi nr.3 si taiem toti multipli cu 3, adica : 3 6(a fost multiplu si lui 2, deci e taiat deja) 9, 12(a fost si multiplu lui 2), 15, 18( a fost si multiplu lui 2),21
– apoi cu nr. 5 si taiem toti multipli cu 5, adica : 5, 10 (a fost multiplu si lui 2) 15 (a fost multiplu si lui 3), 20 ( a fost multiplu si lui 2) 25
– apoi cu nr. 7 si taiem toti multipli cu 7, adica : 7, 21 (a fost si multiplu lui 3 si deci e taiat deja)
Observam ca au ramas nr. 13, 17, 19, 23,
Metoda numerica a lui Eratostene se utilizeaza si astazi dupa 2500 de ani
Teorema fundamentala a aritmeticii TFA : orice numar natural n mai muc sau egal cu 2 se descompune in factori primi in mod unic
sau altfel explicat :
Matematicianul grec ERATOSTENE (275 – 194 î.Hr.) a aplicat o metodă inedită pentru aflarea numerelor prime.
Se scrie șirul numerelor naturale de la 2 până la 100, de exemplu. Se taie din acest șir toți multiplii numerelor prime, astfel:
numărul 2 este prim, vom tăia deci din acest șir toți multiplii lui 2;
3 este număr prim, deci vom tăia toți multiplii lui 3;
tot așa vom proceda și cu 5;
apoi va urma 7;
următorul număr prim este 11; însă, deoarece 7 * 7 = 49, este mai mic decât 100 și 11 * 11 = 121, care este mai mare decât 100, toate numerele care au rămas după ce am tăiat și multiplii de 7 sunt numere prime;
Multiplii lui 2: 4, 6, 8, 10, 12, 14, 16, 18, 20, … 100
Multiplii lui 3: 6, 9, 12, 15, 18, 21, 24, 27, … 99
Multiplii lui 5: 10, 15, 20, 25, 30, 35, 40, 45, … 100
Multiplii lui 7: 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98
După ce eliminăm multiplii de 2, 3, 5 și 7, mai rămân: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, adică exact lista numerelor prime până la 100.