Sedàs d'Eratòstenes

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 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.

Algorisme[modifica | modifica el codi]

  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[modifica | modifica el codi]

Cercar tots els nombres primers fins a 30.

Pas 1. 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, 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. 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. 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. 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}, 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[modifica | modifica el codi]

A l'anterior exemple 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}


On 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'ells. É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, podent afirmant 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[modifica | modifica el codi]

Implementació en C++ http://bloc.gerardfarras.com/wp-content/uploads/2011/12/erastotenes.txt