Deitel_Java_7_27 (La Criba de Eratóstenes en Java)

_____________________________________________________________________________________
Ejercicio 7.26 (La Criba de Eratóstenes) Un número primo es cualquier entero mayor que 1, divisible sólo por sí mismo y por el número 1. La criba de Eratóstenes es un método para encontrar números primos, el cual opera de la siguiente manera:
a) Cree un arreglo del tipo primitivo boolean, con todos los elementos inicializados en true. Los elementos del arreglo con índices primos permanecerán como true. Cualquier otro elemento del arreglo eventualmente cambiará a false.
b) Empezando con el índice 2 del arreglo, determine si un elemento dado es true. De ser así, itere a través del resto del arreglo y asigne false a todo elemento cuyo índice sea múltiple del índice del elemento que tenga el valor true. Para el índice 2 del arreglo, todos los elementos más allá del elemento 2 en el arreglo que tengan índices múltiplos de 2 (los índices 4, 6, 8, 10, etcétera) se establecerán en false; para el índice 3 del arreglo, todos los elementos más allá del elemento 3 en el arreglo que sean índices múltiplos de 3 (los índices 6, 9, 12, 15, etcétera) se establecerán en false; y así sucesivamente. Cuando este proceso termine, los elementos del arreglo que aún sean true indicarán que el índice es un número primo. Estos índices pueden mostrarse. Escriba una aplicación que utilice un arreglo de 1000 elementos para determinar e imprimir los números primos entre 2 y 999. Ignore los elementos 0 y 1 del arreglo.
____________________________________________________________________________________
Solución:
Este código debe guardarse con el nombre UsaEratostenes.java

 import java.util.Scanner;
public class UsaEratostenes
 {  // Abre clase UsaEratostenes
 public static void main(String args[])
 {  // Abre main

 // Se crea un Objeto de tipo Eratostenes
 Eratostenes miObjeto = new Eratostenes();
 
 // Se llama al metodo Principal
  miObjeto.Principal(); 
 }  // Cierra main
 
 }  // Cierra clase UsaEratostenes

ESte código debe guardarse con el nombre Eratostenes.java

 /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                          CRIBA DE ERATOSTENES                            +
   + Este programa muestra numeros primos obtenidos mediante el algoritmo de  +
   + Eratostenes.                                                             + 
   + ENTRADA: No requiere entrada                                             + 
   + SALIDA: Numeros primos                                                   + 
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

  /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   *                                ALGORITMO:                                *
   * Los numeros de 2 a N se consideran todos primos en un principio          *
   *                                                                          * 
   * Desde j = 2 hasta N - 1                                                  *
   *   Desde k = j hasta N/j                                                  *
   *     El Numero k*j se considera no primo.                                 *  
   *                                                                          *
   * Imprime los numeros que al final del proceso aun son primos              *
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ 
  
 public class Eratostenes
 {   // Abre clase Eratostenes
 private int Tamano_Arreglo = 10000000;
 //Basta cambiar este numero para obtener
 // los primos hasta ese limite

 /////////////////////////////////////////////
 // METODO PRINCIPAL
 /////////////////////////////////////////////

 public void Principal()

 { //ABRE PRINCIPAL 
 boolean Arreglo[];
 Arreglo = new boolean[Tamano_Arreglo + 1];
 for ( int i = 1; i < Tamano_Arreglo; i++ )
 Arreglo[i] = true; //EN PRINCIPIO TODOS LOS NUMEROS SE CONSIDERAN PRIMOS

 for ( int j = 2; j <= Tamano_Arreglo; j++ )
 if ( true == Arreglo[j] ) // Para numeros grandes este if hace una 
                           // diferencia de tiempo importante
 for ( int k = 2; k <= (Tamano_Arreglo)/j; k++ )
 Arreglo[k*j] = false;

 // Se llama al metodo Imprime
 Imprime( Arreglo, Tamano_Arreglo );

 } //CIERRA PRINCIPAL 

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

 public void Imprime( boolean A[], int Tamano )

 { //ABRE IMPRIME
 int contador = 0;

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


 System.out.printf("\n\nEstos son los %d numeros primos que hay ", contador);
 System.out.printf("entre 1 y %d\n\n", Tamano_Arreglo);

 int salto = 1; 
 for ( int n = 1; n <= Tamano; n++ )
 { //ABRE FOR
 
 if ( true == A[n] )
 {
 System.out.printf("%4d\t", n);
 salto++;
 }
 if ( 10 == salto )
 {
 System.out.println();
 salto = 1;
 }
 } //CIERRA FOR

 System.out.printf("\n");
 } //CIERRA IMPRIME  

 }   // Cierra clase Eratostenes

El resultado de la ejecución, para Tamano_Arreglo = 1000 es:

Estos son los 168 numeros primos que hay entre 2 y 1000

        2    3    5    7   11   13   17   19 
  23   29   31   37   41   43   47   53   59 
  61   67   71   73   79   83   89   97  101 
 103  107  109  113  127  131  137  139  149 
 151  157  163  167  173  179  181  191  193 
 197  199  211  223  227  229  233  239  241 
 251  257  263  269  271  277  281  283  293 
 307  311  313  317  331  337  347  349  353 
 359  367  373  379  383  389  397  401  409 
 419  421  431  433  439  443  449  457  461 
 463  467  479  487  491  499  503  509  521 
 523  541  547  557  563  569  571  577  587 
 593  599  601  607  613  617  619  631  641 
 643  647  653  659  661  673  677  683  691 
 701  709  719  727  733  739  743  751  757 
 761  769  773  787  797  809  811  821  823 
 827  829  839  853  857  859  863  877  881 
 883  887  907  911  919  929  937  941  947 
 953  967  971  977  983  991  997