Deitel_C++_4.29 (Criba de Eratostenes)

_____________________________________________________________________________________
4.29 (El cedazo de Eratóstenes) Un entero primo es cualquier entero divisible sólo por sí mismo y por el número 1. El método del cedazo de Eratóstenes es uno para localizar números primos. Éste funciona de la siguiente manera:

a) Crea un arreglo con todos los elementos inicializados en 1 (verdadero). Los elementos del arreglos con subíndices primos permanecerán como 1. Los demás elementos, en algún momento se establecerán en cero.
b) Comienza con un subíndice 2, cada vez que se encuentra un elemento del arreglo cuyo valor es 1, repite a lo largo del resto del arreglo y establece en cero cada elemento cuyo subíndice sea múltiplo del subíndice para el elemento con valor de 1. Para un subíndice 2 del arreglo, todos los elementos que pasen de 2 y que sean múltiplos de 2 se establecerán en cero (subíndices 4, 6, 8, 10, etc); para un subíndice de 3, todos los elementos que pasen de 3 y que sean múltiplos de 3, se establecerán en 0 (subíndices 6, 9, 12, 15, etc.); y así sucesivamente.

Cuando éste proceso termina, los elementos de arreglo que aún permanecen en 1, indican que el subíndice es un número primo. Estos subíndices pueden entonces desplegarse. Escriba un programa que utilice un arreglo de 1000 elementos para determinar y desplegar los números primos entre el 2 y el 999. Ignore el elemento 0 del arreglo.
_____________________________________________________________________________________
Solución:
Este programa, la criba de Eratóstenes en C++, es un algoritmo clásico y seguramente lo podrán encontrar en muchas páginas y libros de programación. Sirve para encontrar los números primos que hay entre 1 y N. Para esto se necesita un arreglo de N + 1 entradas, lleno con los valores 0, 1, 2, ... N. El algoritmo concede al principio que todos los números son primos para después colar o cribar el arreglo, se eliminan los múltiplos de 2, de 3, de 5, etc. Lo que queda al final es el conjunto de números primos.
Como dato cultural relacionado no con el programa, sino con Eratóstenes, lea Los Diez Experimentos Más Bellos de la Física, de Manuel Lozano Leyva, en donde se relata de manera muy amena cómo le hizo este genio para calcular, con admirable exactitud, el radio de la tierra hace casi 23 siglos.

 #include<iostream>
 using namespace::std;

 const int Tamano_Arreglo = 1000;
//Basta cambiar este numero para obtener
// los primos hasta ese limite


 void Imprime( int A[], int Tamano);

 int main()

 { //ABRE MAIN
 int Arreglo[Tamano_Arreglo + 1] = { 0, 0};

 for ( int i = 1; i <= Tamano_Arreglo; i++ )
 Arreglo[i] = 1; //EN PRINCIPIO TODOS LOS NUMEROS SE CONSIDERAN PRIMOS

 for ( int j = 2; j <= Tamano_Arreglo; j++ )
 for ( int k = 2; k <= (Tamano_Arreglo)/j; k++ )
 Arreglo[k*j] = 0;

 Imprime( Arreglo, Tamano_Arreglo );

 return 0;

 } //CIERRA MAIN


//////////////////////////////////////////////
// IMPRIME
//////////////////////////////////////////////

 void Imprime( int A[], int Tamano )

 { //ABRE IMPRIME
 int contador = 0;

 for ( int m = 1; m <= Tamano; m++ )
 { //ABRE FOR
 if ( 1 == A[m] )
 contador++;
 } //CIERRA FOR


 cout <<"\n\nEstos son los " << contador << " numeros primos que hay ";
 cout <<"entre 1 y " << Tamano << endl;

 for ( int n = 1; n <= Tamano; n++ )
 { //ABRE FOR

 if ( 1 == A[n] )
 {
 cout <<" " << n << "\t";
 }
 } //CIERRA FOR

 cout << endl <<endl;
 return;
 } //CIERRA IMPRIME