Sedàs d'Eratòstenes

De Viquipèdia

En matemàtiques, el sedàs d'Eratòstenes és un antic algorisme per cercar tots els nombres primers fins a un determinat enter. Va ser creat per Eratòstenes (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.

[edita] Algorisme

  1. Escriviu una llista A amb els números des del 2 fins a l'enter més gran N que volgueu calcular.
  2. El primer nombre de la llista és un nombre primer. Anoteu-lo en una llista de nombres primers, B.
  3. Esborreu 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} torneu 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.

[edita] Exemple

Cerqueu tots els nombres primers fins a 30.

Pas 1. Escriviu una llista A amb els números des del 2 fins el 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, anoteu-lo 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. Esborreu 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, torneu al punt 2 de l'algorisme.

Pas 5. El 3 és un nombre primer, anoteu-lo 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. Esborreu 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, anoteu-lo a la llista B.

Llista A:             5     7             11     13             17     19             23     25             29    
Llista B: 2 3 5

Pas 9. Esborreu 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}, continueu 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