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:
Ejemplo: Para n=20
- 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. |
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 |
