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