con la lógica del ejemplo 4.1 (desborde contadores para no usar CONTINUE ni BREAK), muestro un algoritmo practico,
Ejemplo #5LISTAR LOS #S PRIMOS hasta un valor NUsa uno de tanto algoritmos de Criba o Colador De Números Primos, recordemos que el primer Colador de primos lo creo Eratóstenes hace mucho mucho tiempo (prehistoria)
El programa debe retornar, los números primos menores a N
Es importante analizar los siguientes casos
Si n es menor que 10 debe mostrar la siguiente lista de #s primos:
{ 2, 3, 5, 7 } (4 en total)
Si n es menor que 100, (26 en total)
{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97 }
Si n es menor que 1,000 (168 en total)
{ 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 }
Si n es menor que 10,000 son 1229
{ 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, 1009, 1013, ..., 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973 }
Si n es menor que 100,000 son 9592 ...
¿Que noto a simple vista? que el único primo par es el 2, entonces podemos pensar que un colador o generador de primos debe descartar los números pares o empezar a buscar solamente dentro los números impares 2*n+1 ó 2*n-1, como el código agrega los 2 primeros números primos, basta con chequear desde x = 6 * n - 1
se observa también que al incrementar N, la lista crece rápidamente, entonces si ejecuta el código con N mayor a 1000000 podrá ver que se demora muchísimo tiempo
El código de abajo se codifico con muchas variables para facilitar la depuración, próximamente incluiré código fuente simplificado del mismo y usando BREAK, ...
SI USTED DESEA APRENDER MAS, corra el programa paso a paso, se ha demostrado que un método para facilitar el aprendizaje o adquirir lógica de programacion es "Debugiar" o Depurar un código, ademas observa el mecanismo del algoritmo
El algoritmo indicado abajo no es eficiente, solo sirve para demostrar como usar el desborde del contador de cada FOR para salir del bucle sin usar BREAK o CONTINUE, ni mucho menos el GoTo
PASOS
1: declarar un objeto tipo LISTA, ya que este objeto en JAVA es de tipo dinámico el cual podrá almacenar miles de números solo con la limitante de su memoria RAM
cálculos aproximados, si me equivoco me corrigen por favor
Si al correr el programa se tiene 1 GiBytes libre en RAM y como un GiBytes equivale a
2^30 bytes = 1024 mebibyte (MiG) = 1073741824 bytes
y como cada elemento de la lista es un LONG de 8 Bytes,
podemos almacenar 1073741824 bytes / 8 bytes = 134,217,728 ~ 134 mil números primos y cada uno entre [0, ..., 2^(8*8-1)-1= 9,223,372,036,854,775,807] que es el limite de LONG para números enteros positivos en java
pero si almacenamos la salida en un archivo es decir cada primo encontrado lo escribimos en un archivo texto podemos colocar millones de #s primos, solo nos limitaría la capacidad de nuestro disco duro
Si tenemos libre un 1 tebibyte osea 2^40 bytes = 1 099 511 627 776 en nuestro disco duro
y como LONG maneja hasta 19 dígitos + un espacio = 20 caracteres y so almacenados cada dígito en ASCCI de 8 bytes cada impresión podría ocupar hasta 8*20 = 160 bytes,
con este razonamiento entonces podemos almacenar aproximadamente
1099511627776 / 160 = 6,871,947,673.6 impresiones ~
6.8 mil millones de números primos pero es mas realmente, por que no todos los primes inician en 19 dígitos
2: adherir el 2 y 3 como los dos primeros primos,, ya que algoritmo cola el primer primo a partir de 5
3: desplegar en pantalla los dos primeros #s primos
4: declarar variables de cada expresión del algoritmo para facilitar la depuración
(N, contador primer bucle)
(K, contador segundo bucle)
(maxK, limite segundo bucle)
(J, contador primo)
...
5: iniciar un bucle en pasos de 1 y entre N=1 hasta N<=100 ó 1000 o el que desee
6: evaluar la expresión X=6*N-1
...
import java.util.ArrayList;
public class UnColadorDePrimos{
public static void main
(String[] args
) { // Crea un objeto tipo lista
// Adhiere 2 a la lista
lista.add(2.);
// Adhiere 3 a la lista
lista.add(3.);
System.
out.
println(lista.
get(0)); System.
out.
println(lista.
get(1)); // variables valor para FOR n
// Contador para FOR n
int n;
// rango FOR n [1, 6] pasos en 1
int minN = 1;
int maxN = 100;
int incrN = 1;
// variables valor para FOR k
// Contador para FOR k
int k;
// rango FOR n [1, j] pasos en 1
int minK = 1;
int maxK;
int incrK = 1;
// Contador, maximo valor para FOR k, inicialmente en 2
int j = 2;
double x;
for (n = minN; n <= maxN; n = n + incrN) {
x = 6 * n - 1;
maxK = j;
boolean desbordeK = false;
for (k = minK; k <= maxK; k = k + incrK) {
desbordeK = false;
double numero = lista.get(k - 1);
double testA = numero;
double testB
= Math.
sqrt(x
); boolean test1 = (testA > testB);
if (test1 == true) {
j = j + 1;
lista.add(x);
System.
out.
println(lista.
get(j
- 1)); x = 6 * n + 1;
// Abandonar ciclo
desbordeK = true;
k = maxK + incrK;
} else {
double testC = x / numero;
double testD
= Math.
floor(x
/ numero
); boolean test2 = (testC == testD);
if (test2 == true) {
x = 6 * n + 1;
desbordeK = true;
// Abandonar ciclo
k = maxK + incrK;
}
}// end if
}//next for k
if (desbordeK != true) {
j = j + 1;
lista.add(x);
System.
out.
println(lista.
get(j
- 1)); }
maxK = j;
boolean desbordeK2 = false;
for (k = minK; k <= maxK; k = k + incrK) {
desbordeK2 = false;
double numero = lista.get(k - 1);
double testA = numero;
double testB
= Math.
sqrt(x
); boolean test1 = (testA > testB);
if (test1 == true) {
j = j + 1;
lista.add(x);
System.
out.
println(lista.
get(j
- 1)); // Abandonar ciclo
desbordeK2 = true;
k = maxK + incrK;
} else {
double testC = x / numero;
double testD
= Math.
floor(x
/ numero
); boolean test2 = (testC == testD);
if (test2 == true) {
// Abandonar ciclo
k = maxK + incrK;
}
}// end if
}//next for k
if (desbordeK2 != true) {
j = j + 1;
lista.add(x);
System.
out.
println(lista.
get(j
- 1)); }
}//next for n
}// main
}// class
