Garbell d'Eratòstenes. X54043

Feu la funció eratostenes (N) tal que, donat un enter N, retorni un vector amb tots els nombres primers fins a N segons l’algoritme del Garbell d’Eratòstenes.

Aquesta tècnica és molt simple, i consisteix en posar tots els números de 2 fins a $N$ i anar marcant els que no són primers de la següent manera:

1. Marquem tots els elements com a primers.

2. Anem al primer número marcat. Sigui $p$ aquest número.

3. Anem saltant de $p$ en $p$ elements i anem desmarcant els elements a la p-èssima posició com a divisibles (no-primers).

4. Ho fem mentre hi hagi números per desmarcar.

Per exemple, si N=10, tindríem primer:

Ara busquem el primer element marcat de la llista. En aquest cas és el 2. Ara anem saltant de 2 en 2 i desmarquem es elements per on passem:

Ara anem al següent element marcat, en aquest cas el 3, i fem la mateixa operació:

En aquest cas només hem desmarcat el 9, ja que el 6 l’havíem desmarcat abans, ja que és múltiple de 2. Ara anem al següent element marcat, en aquest cas és el 5:

Aquí ja podem parar, ja que si anem al següent element marcat (el 7), quan saltem de 7 en 7 ja sortirem del vector. Per tant, ara la funció ha de tornar un vector amb els elements marcats. En aquest cas, el vector ha de contenir $2,3,5, 7$.

Entrada

Un enter N.

Sortida

Un vector amb els nombres primers fins a N, calculats amb l’algoritme del garbell d’Eratòstenes.