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