Seta lui Eratostene

Sita Eratostene este un algoritm antic pentru calcularea tabelelor numerelor prime până la un anumit număr predeterminat. Acest principiu își datorează numele matematicianului Eratostene din Cirene , care a fost creatorul acestuia. Este încă folosit ca algoritm de număr prim de multe programe de calculator datorită simplității sale. Deși nu este complet eficient, de fapt, este destul de simplu de tradus în orice limbaj de programare .

Algoritm

Procedura este următoarea: toate numerele naturale sunt scrise începând de la $2$ ${\ displaystyle 2}$ $2$ pana cand $n$ ${\ displaystyle n}$ $n$ într-o listă numită sită. Apoi, toți multiplii primului număr al sitei sunt șterse (cernute) (exclusiv el însuși). Primul număr ne șters mai mare decât este apoi luat $2$ ${\ displaystyle 2}$ $2$ iar operația se repetă cu numerele care urmează, continuând până când operația este aplicată ultimului număr care nu a fost șters. Restul numerelor sunt numere prime mai mici sau egale cu $n$ ${\ displaystyle n}$ $n$ .

Este ca și cum s-ar folosi site cu ochiuri mai mari treptat: primul permite numai numere non-multiple de $2$ ${\ displaystyle 2}$ $2$ , al doilea numai non-multipli ai $3$ ${\ displaystyle 3}$ $3$ , si asa mai departe.

In caz $n=50$ ${\ displaystyle n = 50}$ $n = 50$ de exemplu, procesul de cernere se termină cu numărul $7$ ${\ displaystyle 7}$ $7$ deoarece $7$ ${\ displaystyle 7}$ $7$ este maximul prim al cărui pătrat nu depășește $50$ ${\ displaystyle 50}$ $50$ și se poate dovedi că procesul de cernere pentru a căuta primul până la un anumit număr $n$ ${\ displaystyle n}$ $n$ încetează întotdeauna când se depășește rădăcina pătrată a lui $n$ ${\ displaystyle n}$ $n$ . Într-adevăr, fiecare număr $la$ ${\ displaystyle a}$ $la$ a sitei inițiale, care conține toate numerele naturale care nu depășesc un dat $n$ ${\ displaystyle n}$ $n$ , cade din sită care corespunde celui mai mic dintre separatoarele sale prime .

Dacă indicăm cu $p$ ${\ displaystyle p}$ $p$ cel mai mic divizor prim al $la$ ${\ displaystyle a}$ $la$ avem:

a=p\cdot r{\text{ con }}r\geq p.

{\ displaystyle a = p \ cdot r {\ text {con}} r \ geq p.}

a = p \ cdot r {\ text {cu}} r \ geq p.

Rezultă că $a=p\cdot r\geq p\cdot p=p^{2}$ ${\ displaystyle a = p \ cdot r \ geq p \ cdot p = p ^ {2}}$ $a = p \ cdot r \ geq p \ cdot p = p ^ {2}$ , de la care $p$ ${\ displaystyle p}$ $p$ este întotdeauna mai mică sau egală cu rădăcina pătrată a $la$ ${\ displaystyle a}$ $la$ .

O implementare a algoritmului lui Eratostene în Haskell care calculează al n-lea număr prim:

 takePrime :: Int -> Int
takePrime = takePrimeAux [ 2 .. ]
  Unde
    takePrimeAux :: [ Int ] -> Int -> Int
    takePrimeAux ( l : ls ) 1 = l
    takePrimeAux ( l : ls ) n = takePrimeAux ( filter ( \ x -> ( mod x l ) / = 0 ) ls ) ( n - 1 )

Exemplu

Pentru a găsi toate numerele prime mai mici decât $30$ ${\ displaystyle 30}$ $30$ , puteți proceda după cum urmează:

Scrieți lista tuturor numerelor întregi din $2$ ${\ displaystyle 2}$ $2$ la $30$ ${\ displaystyle 30}$ $30$ :

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Ștergeți din listă multiplii de $2$ ${\ displaystyle 2}$ $2$ :

 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29

Primul număr de pe listă după $2$ ${\ displaystyle 2}$ $2$ si $3$ ${\ displaystyle 3}$ $3$ ; ștergeți multiplii de $3$ ${\ displaystyle 3}$ $3$ :

 2 3 5 7 11 13 17 19 23 25 29

Primul număr de pe listă după $3$ ${\ displaystyle 3}$ $3$ si $5$ ${\ displaystyle 5}$ $5$ ; ștergeți din listă multiplii rămași ai $5$ ${\ displaystyle 5}$ $5$ :

 2 3 5 7 11 13 17 19 23 29

Primul număr de pe listă după $5$ ${\ displaystyle 5}$ $5$ si $7$ ${\ displaystyle 7}$ $7$ , deoarece nu mai există multipli, numerele rămase sunt numerele prime pe care le căutam.

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe site-ul Eratostene

linkuri externe

( EN ) Sider of Eratosthenes , pe Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică