7/23/2019 Practica1-Criba de Eratostenes

http://slidepdf.com/reader/full/practica1-criba-de-eratostenes 1/2

Práctica con PSP0

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos

menores que un número natural dado n. Se llena una tabla con todos los números

naturales comprendidos entre 2 y n  siendo n un número leído por teclado, atendiendolos siguientes limitantes 1 < n <= 10 , y se van convirtiendo en cero números que no

son primos de la siguiente manera:

Comenzando por el 2, se convierten en cero todos sus múltiplos; comenzando de nuevo,

cuando se encuentra un número entero que no ha sido convertido en cero, ese número es

declarado primo, y se procede a convertir en cero todos sus múltiplos, así

sucesivamente. El proceso termina cuando el cuadrado del mayor número confirmado

como primo es mayor que n.

Proceso de cribaDeterminemos, mediante el siguiente ejemplo, el proceso para determinar la lista de los

números primos menores de 20.

1) 

Primer paso : se llena un arreglo con los números naturales comprendidos entre

2 y 20

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2) 

Segundo paso:  Se toma el primer número , no marcado, como número primo.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

3)  Tercer paso:  Se convierten en cero todos los múltiplos del número que se acaba

de indicar como primo.

2 3 0  5 0  7 0  9 0  11 0  13 0  15 0  17 0  19 0 

4) 

Cuarto paso:   Si el cuadrado del primer número que no ha sido marcado es

inferior a 20, entonces se repite el segundo paso. Si no, el algoritmo termina, ytodos los enteros no marcados son declarados primos.

Como 3² = 9 < 20, se vuelve al segundo paso:

2 3 0  5 0  7 0  0  0  11 0  13 0  0  0  17 0  19 0 

En el cuarto paso, el primer número que no ha sido tachado ni marcado es 5. Como su

cuadrado es mayor que 20, el algoritmo termina y se consideran primos todos los

números que no han sido marcados.

7/23/2019 Practica1-Criba de Eratostenes

http://slidepdf.com/reader/full/practica1-criba-de-eratostenes 2/2

Como resultado se obtienen e imprimen los números primos comprendidos entre 2 y 20,

y estos son:

2, 3, 5, 7, 11, 13, 17, 19.

Se pide:

Elaborar un programa en lenguaje C que encuentre e imprima todos los números primos

comprendidos entre 2 y n, utilizando el algoritmo de la criba de Eratóstenes, atendiendo

las siguientes indicaciones:

a) 

Utilizar programación orientada a objetos, crear una clase denominada Criba,

con un campo arreglo.

 b) 

Utilizar un arreglo de enteros de máximo 100 elementos, por lo que deberá

validar que el usuario no introduzca un número mayor que la cantidad máxima.

c) 

Escribir una función int divisor(int, int),  que reciba dos números

enteros y devuelva un 1 (uno) si el primer número es divisor del segundo o un 0  

(cero) si no lo es, esta función la utilizará en el programa para encontrar los

divisores del número evaluado.

d)  Se evaluará que el programa siga el algoritmo de la criba de Eratóstenes

 planteado en este documento.

e)  Almacenar los resultados en un archivo de texto

Entregar:

1. 

El código fuente del programa,2.  Respaldo del Process Dashboard

3. 

Captura de pantalla de la ejecución del programa.

4.  Captura de pantalla de pruebas realizadas

5.  Revisar los tiempos y los defectos.