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.

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

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