Sedàs d'Eratòstenes

En matemàtiques, el sedàs d'Eratòstenes o garbell d'Eratòstenes és un antic algorisme per cercar tots els nombres primers fins a un determinat enter. Nicòmac de Gerasa descriu un mètode d'aritmètica per trobar els nombres primers, atribuint-lo a Eratòstenes de Cirere (276-194 aC), un matemàtic de l'antiga Grècia. És un mètode molt senzill però actualment n'existeixen de més ràpids, com el sedàs d'Atkin.

Realització del garbell d'Eratòstenes per als nombres naturals més petits que 120.

Aquest mètode és bàsic per a poder desenvolupar l'aritmètica pitagòrica de la divisibilitat, basada en el teorema fonamental de l'aritmètica i en l'existència d'un gran nombre de nombres primers.

Algoritme

1. S'escriu una llista A amb els nombres des del 2 fins a l'enter més gran $N$ que es vulgui avaluar.
2. El primer nombre de la llista és un nombre primer. S'enregistra a la llista de nombres primers, B.
3. S'esborra de la llista A el primer nombre i els seus múltiples.
4. Si el primer nombre de la llista A és més petit que ${\sqrt {N}}$ es torna al punt 2.
5. Els nombres de la llista B i els que queden a la llista A són tots els nombres primers cercats.

Exemple

Cal cercar tots els nombres primers fins a 30.

Pas 1. Cal escriure una llista A amb els nombres des del 2 fins al 30.

Llista A:

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

Pas 2. El 2 és un nombre primer, cal enregistrar aquest nombre a la llista B.

Llista A:

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

Llista B:

2

Pas 3. Cal esborrar de la llista A el 2 i els seus múltiples.

Llista A:

3

5

7

9

11

13

15

17

19

21

23

25

27

29

Llista B:

2

Pas 4. $3<{\sqrt {30}}$, per tant, s'ha de tornar al punt 2 de l'algorisme.

Pas 5. El 3 és un nombre primer, s'ha d'enregistrar a la llista B.

Llista A:

3

5

7

9

11

13

15

17

19

21

23

25

27

29

Llista B:

2

3

Pas 6. Cal esborrar de la llista A el 3 i els seus múltiples.

Llista A:

5

7

11

13

17

19

23

25

29

Llista B:

2

3

Pas 7. $5<{\sqrt {30}}$, per tant, torneu al punt 2 de l'algorisme.

Pas 8. El 5 és un nombre primer, s'ha d'enregistrar a la llista B.

Llista A:

5

7

11

13

17

19

23

25

29

Llista B:

2

3

5

Pas 9. Cal esborrar de la llista A el 5 i els seus múltiples.

Llista A:

7

11

13

17

19

23

29

Llista B:

2

3

5

Pas 10. $7\not <{\sqrt {30}}$, cal continuar amb el punt 5 de l'algorisme.

Pas 11. Els nombres de la llista B i els que queden de la llista A són els nombres primers fins a 30.

Nombres primers fins a 30: 2, 3, 5, 7, 11, 13, 17, 19, 23 i 29

Final de l'algorisme

A l'exemple anterior, s'ha vist que el punt finalitzant de l'algorisme, el punt 5, s'aconsegueix quan el nombre primer avaluat (7 al final de l'exemple) és major que l'arrel quadrada de l'últim nombre de la llista, això era: $7\not <{\sqrt {N}}$. És evident que quan s'arriba a aquesta situació amb un nombre primer, l'algorisme no té continuació en cap cas, ja que no es pot trobar un nombre sencer a la llista que, dividit pel 7 en aquest cas o per qualsevol dels següents, doni un resultat sencer.

En aquests casos, s'ha de complir que:

$n\not \leq {\sqrt {N}}$

en què elevant al quadrat i canviant a la inequació contrària (i vertadera en aquest cas):

$n^{2}>N$

Dividint per n a ambdós costats, és evident que:

$n>{\frac {N}{n}}>0$

S'avalua l'anterior inequació tenint en compte que ja s'han comprovat tots els nombres primers menors a n als anteriors passos, assegurant a cada pas que no era múltiple de cap d'aquests. És evident que la divisió proposada a la inequació dona resultat <n, és a dir, donaria com a resultat un nombre menor que el que s'està avaluant, i es pot afirmar, doncs, que no era divisible entre cap dels nombres primers anteriors, ja que si s'hagués donat aquest cas, l'algorisme l'hagués descartat. Després d'aquesta avaluació es passa al punt 5. llistat a l'exemple. Això és passar a llistar els nombres restants una vegada s'ha incomplet la inequació, ja que només poden dividir-se per si mateixos, finalitzant així l'algorisme.

Enllaços externs

• Implementació en C++ http://bloc.gerardfarras.com/wp-content/uploads/2011/12/erastotenes.txt Arxivat 2016-03-03 a Wayback Machine..