1Eva_IT2008_T2 Criba de Eratóstenes

1ra Evaluación I Término 2008 – 2009. Julio 08, 2008 /ICM00794

Tema 2 (20 puntos). Una forma de hallar todos los números primos menores que un número natural n, es el método de la “Criba de Eratóstenes” que consiste en lo siguiente:

  • Se forma un vector con todos los números naturales entre 2 y n
  • Se tachan todos los múltiplos de 2 que son menores que n, luego se tachan los múltiplos de 3 que son menores que n, y así sucesivamente.
  • El procedimiento se repite hasta alcanzar todos los múltiplos de los números naturales menores que n.
  • Los números no tachados corresponden a los números primos.

Elabore un algoritmo que, dado un número entero positivo n mayor que 1, muestre los números primos encontrados con el método descrito.

Ejemplo: Para n=20

i criba[i]
2 1
3 1
4 0
5 1
6 0
7 1
8 0
9 0
10 0
11 1
12 0
13 1
14 0
15 0
16 0
17 1
18 0
19 1
20 0

Primos: 2, 3, 5, 7, 11, 13, 17, 19