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