Java - La Criba de Erastote es entre m y n con m<n

 
Vista:

La Criba de Erastote es entre m y n con m<n

Publicado por OSCAR (4 intervenciones) el 30/08/2020 00:58:26
Quiero consultar .... estoy trabado en el razonamiento para el desarrollo de una criba de Erastote es entre m y n con m menor n .....
mi principal problema está en que cuando empiezo a depurar una lista por ejemplo de 2000 a 2010 ... va bien con 2 luego con 3 .... pero no sé cómo hacer para evitar depurar por 4 que es múltiplo de dos entonces no me sirve ... y tampoco el límite hasta cuándo buscar ... múltiplos

Ayuda !!!
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Kabuto
Val: 2.717
Oro
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

La Criba de Erastote es entre m y n con m<n

Publicado por Kabuto (706 intervenciones) el 30/08/2020 02:18:58
Hola, no se como lo estarás haciendo tú.

Creo que lo ideal es usar un vector de booleanos.
Iniciamos todos en valor true y comenzamos desde la posición 2 a comprobar que posiciones son múltiplos.
Las que lo sean, las pasamos a valor false.

Terminada con esta primera posición, pasamos a la siguiente que aún tenga valor true. Y repetimos el proceso de eliminar múltiplos.

Este proceso ha de continuar hasta que la siguiente posición a cribar, su cuadrado sea mayor que el valor último de la tabla, es decir, el valor n según tu enunciado.

Eso pondría fin al proceso de criba, y ya solo quedaría mostrar los valores de las posiciones que conservan valor true, y que se encuentren entre m y n.

He escrito este código, y parece funcionar correctamente:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Criba {
 
	public static void main(String[] args) {
 
		Scanner teclado = new Scanner(System.in);
		System.out.println("Valor inicial para la Criba: ");
		int m = teclado.nextInt();
		System.out.println("Valor final para la Criba: ");
		int n = teclado.nextInt();
 
 
		//Inicializamos vector de valores todos a true
		boolean[] valores = new boolean[n + 1];
		for (int i = 0; i < valores.length; i++)
			valores[i] = true;
		//Comenzamos cribando por el 2
		int cribando = 2;
		//Algoritmo termina cuando el número que toca cribar, su cuadrado es superior a n
 
		while ((cribando * cribando) <= n) {
 
			for (int i = (cribando + 1); i < valores.length; i++)
				if (i % cribando == 0)
					valores[i] = false; //Múltiplo hallado, eliminamos
 
			//Proceso de criba para valor actual, terminado.
			//Buscamos el primer valor No Eliminado , para siguiente criba
			for (int i = cribando + 1; i < valores.length; i++)
				if (valores[i] == true) {
					cribando = i;
					break;
				}
		}
 
		///Criba terminada.
		//Mostramos valores superviviente a la criba, entre los limites elegidos por usuario
		System.out.println(String.format("\nPrimos encontrados entre %d y %d\n", m, n));
 
		for (int i = m; i <= n; i++)
			if (valores[i] == true)
				System.out.print(i + " ");
 
		teclado.close();
	}
 
}

Pantalla sale este resultado, que creo es correcto:
1
2
3
4
5
6
7
8
Valor inicial para la Criba:
1945
Valor final para la Criba:
2010
 
Primos encontrados entre 1945 y 2010
 
1949 1951 1973 1979 1987 1993 1997 1999 2003
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Rodrigo
Val: 1.626
Plata
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

La Criba de Erastote es entre m y n con m<n

Publicado por Rodrigo (437 intervenciones) el 30/08/2020 05:51:49
Una proposicion de mejora a lo presentado:

Las iteraciones por todos los enteros y la operacion modulo del ciclo de la linea 22-24 son superfluas.

En vez de buscar los multiplos, se pueden construir ellos y eliminarlos con algo parecido a:

1
2
3
for( int mutiplo = cribando * 2; multiplo <= n; multiplo += cribando ) {
     valores[multiplo] = false;
}

Con esta proposicion, el ciclo hace menos vueltas y no es necesario comparar en cada vuelta de ese ciclo.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
1
Comentar

La Criba de Erastote es entre m y n con m<n

Publicado por oscar (4 intervenciones) el 31/08/2020 01:09:29
Mí problema en el ejercicio es que tengo que hacer la cargar desde m hasta n .... osea si m es 2000 . y n 2010 ... será un vector que va desde 2000 2001 2002 2003... 2010 y así ... y evitar hacer pasadas desde el 2
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Kabuto
Val: 2.717
Oro
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

La Criba de Erastote es entre m y n con m<n

Publicado por Kabuto (706 intervenciones) el 31/08/2020 01:41:50
Interesante propuesta
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

La Criba de Erastote es entre m y n con m<n

Publicado por oscar (4 intervenciones) el 31/08/2020 01:06:37
Perfecto comprendo totalmente la lógica ... ahora yo tengo una cuestión y es la de la eficiencia de cargar un vector de booleanos desde 2 hasta n ... cuando lo que me están pidiendo en realidad es hacer las pasadas de m .... hasta n ... si tengo que cargar desde m = 2000 ... y n= 2010 ... tendría un vector de la siguiente manera 2000 2001 .... 2010 ... o en caso de usar booleanos un vector te tamaño 10 ... osea de 0 a 9 completo de true ... pero obviamente ahí esta opción es poco eficiente porque ya no tengo los valores de referencia
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Kabuto
Val: 2.717
Oro
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

La Criba de Erastote es entre m y n con m<n

Publicado por Kabuto (706 intervenciones) el 31/08/2020 01:39:01
Comenzando desde el 2, luego 3, luego 5 (porque el 4 ha sido eliminado al cribar por el 2), etc... te aseguras de eliminar correctamente los números que NO son primos, que es el propósito de la Criba de Eratóstenes.

Si empiezas desde valores superiores, no tienes garantías de que estés quedando solo con números primos.

Imagina que pido buscar los primos entre 2001 y 2006.
Si aplicase un algoritmo similar al anterior, pero empezando por el 2001 a eliminar múltiplos:
¿2002 es múltiplo de 2001? No, por lo tanto no lo elimino.
El 2002 "sobrevive" a la criba...

Pues no hace falta que continúe, esto ya está mal. 2002 no es primo, por el simple hecho de ser un número par.
Por cierto, esa es otra forma de agilizar el proceso, trabajar solo con números impares. Excepto el 2, ningún otro par es primo.

En definitiva, para eliminar correctamente números compuestos (los que no son primos) hay que comenzar desde el 2.

Aunque bueno, no soy matemático y quizás haya otra forma. Pero la Criba de Eratóstenes por definición, actúa comenzando desde el 2. Así que si nos piden aplicar dicho algoritmo, pues no podemos cambiar eso.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
Imágen de perfil de Rodrigo
Val: 1.626
Plata
Ha mantenido su posición en Java (en relación al último mes)
Gráfica de Java

La Criba de Erastote es entre m y n con m<n

Publicado por Rodrigo (437 intervenciones) el 31/08/2020 02:34:40
Se puede resolver usando el metodo de la criba y usando menos memoria mediante 2 arreglos,
- Arreglo "primos", para conservar los numeros primos hasta la raiz cuadrada de n
- Arreglo "segmento" para el rango m .. n, de tamano n-m+1, por ejemplo si m = 10000 y n = 10002 el arreglo es de tamano 3

Se itera sobre el primer arreglo para descubrir los numeros primos, se marca como Eratostenes indica en el. Por cada vuelta se va a obtener el primo i-esimo, y con este se itera para hacer marcas sobre el segundo arreglo tambien.

La idea es algo asi (puede tener errores) ..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
inicializar primos[x] = true para todo x [0..sqrt(n)]
inicializar segmento[y] = true para todo y [0 .. m-n+1]
 
for( int i = 2; i * i <= n; i++ ) {
   if( primos[i] == true ) { // i es primo, marcar como no primos todos los multiplos
       for( int multiplo = i * i; multiplo <= n; multiplo += i ) {
           // marca en el arreglo de primos
           if( multiplo * multiplo <= n ) {
               primos[multiplo] = false;
           }
           // marca en el segmento
           if( multiplo >= m ) {
               segmento[ multiplo - m ] = false;
           }
       }
   }
}
 
// Recorrer la tabla segmento, los numeros aun con marca true son primos.
for( int i = m; i <= n; i++ ) {
    if( segmento[ i - m ] == true ) {
        escribir el numero i como primo
    }
}

Con esto se reduce la cantidad de memoria usada de O(n) a O(max( sqrt(n), n-m+1 ))
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

La Criba de Erastote es entre m y n con m<n

Publicado por oscar (4 intervenciones) el 31/08/2020 02:55:17
Ahora que lo decís ... Podría crear un arreglo con los posibles múltiplos desde 2 hasta √n además de mí arreglos con los números desde m hasta n ... cómo no hay otro primo par elimino en su totalidad los pares .... luego avanzo a 3 elimino pares de 3 .... cuando en mí arreglo quiera probar 4 voy a comprobar que ese múltiplo no sea un compuesto comprobando que 4 % 3 != 0 hasta 4% 2 .... en caso de que encuentre uno podría avanzar y así comprobar ... pero también sería algo ineficiente ... aunque creo que así sería algo más rápido
Otra sería que depure ambas lista la lista de múltiplos llamabdo al método criba tradicional ... pero bueno nosé ahí ya se me mezcla todo jajaj pasa que el ejercicio pide mantener el concepto de la criba
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar