Garbell de Eratóstenes

Archiu:Sieve of Eratosthenes animation.gif

Animació del garbell de Eratóstenes per a número primo menors que 120. S'inclou l'optimisació de començar pels quadrats d'número primo.

La ereja d'Eratóstenes és un algoritme que permet trobar molts número primo menors que un número natural donat. Es forma una taula en tots els número natural compresos entre 2 i n, i es van tachant els números que no són primers de la següent manera: Començant pel 2, es tachen tots els seus múltiples; començant de nou, quan es troba un número entero que no ha segut tachat, eixe número és declarat primer, i es procedix a tachar tots els seus múltiples, aixina successivament. El procés termina quan el quadrat del següent número confirmat com a primer és major que n.

Procés de garbell

Determinem, per mig del següent eixemple, el procés per a determinar la llista dels número primo menors de 20.

1. Primer pas: llistar els número natural compresos entre 2 fins al número que es desige, en este cas, fins al 20.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

2. Segon pas: es pren el primer número no rayado ni marcat, com a número primo.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

3. Tercer pas: es tachen tots els múltiples del número que s'acaba d'indicar com a primer.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

4. Quart pas: si el quadrat del primer número que no ha segut rayado ni marcat és inferior a 20, llavors es repetix el segon pas. Si no, l'algoritme termina, i tots els sancers no tachats són declarats cosins.

Com 3² = 9 < 20, es torna al segon pas:

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

En el quart pas, el primer número que no ha segut tachat ni marcat és 5. Com el seu quadrat és major que 20, l'algoritme termina i es consideren primers tots els números que no han segut tachats.

Com a resultat s'obtenen els número primo compresos entre 2 i 20, i estos són: 2, 3, 5, 7, 11, 13, 17, 19.

Refinament

Un refinament del garbell consistix en tachar els múltiples del k-ésimo número primo p_k, començant per p_k² puix en els anteriors passos s'havien tachat els múltiples de p_k corresponents a tots els anteriors número primo, açò és, 2p_k, 3p_k, 5p_k,…, fins a (p_k-1)p_k. L'algoritme acabaria quan p²_k>n ya que no hi hauria res que tachar.

Un atre refinament consistix en generar una llista solament en número impar (puix els número par distints de 2 se sap que no són primers), i anar tachant els múltiples dels número primo per mig d'increments de 2p, és dir, els múltiples impars (2k+1)p de cada primer p. Açò apareix en l'algoritme original.

Pseudocódigo

Sobre la notació:

• $\lfloor x\rfloor$ és la funció part sancera de $x$
• $a÷b$ és el cocient de dividir $a$ entre $b$

Per a la seua implementació en una computadora, normalment es maneja un vector de tipo llògica en $n$ elements. D'esta manera, la posició $i$ conté el valor Verdader com a representació de que $i$ ha segut marcat i Fals en un atre cas.

Vore també

• Test de primalidad