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.

Observació

Només cal que enviïs el fitxer amb la funció (i les funcions auxiliars que hagis fet) que et demanem i prou. El fitxer main.R et pot servir per a fer la teva solució, però no cal que n’enviïs el contingut.

Entrada

Un enter N.

Sortida

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