Primos Circulares

[carvear]

Gente, dado el problema. Devolver todos los primos circulares menores a 1000 (Utilizando Threads).
Donde un primo circular es que todas sus rotaciones sean primos, por ejemplo: 197 es primo circular, ya que 197, 971 y 719 son primos.

Corrijanme:
1 - Seria bueno utilizar Threads para ver todas las combinaciones que tiene un numero para ver si es primo.

2 - Seria bueno utilizar Threads para ver cada numero del 1 al 1000 si son primos.

3 - O donde y como utilizarían Threads ustedes.

4 - Lo desarrolle tirando un thread por cada numero del 1 al 1000, que les parece eso?

5 - Respecto a la implementacion, hice lo siguiente, pero tarda mucho el programa en terminar, seguro hay algo que no estoy haciendo bien. Les pego la clase abajo.

public class MyThread extends Thread {
static List<Integer> lista_salida = new ArrayList<Integer>();

/* Constructor de la clase */
public MyThread(String str){
super(str);
}

/* Muestra por pantalla los elementos de una lista */
private static void mostrar_lista_elementos(List elementos){
int i=0;
while(i < elementos.size()){
System.out.println(elementos.get(i));
i++;
}
}

/* Codigo a ser ejecutado por Threads */
public void run(){
Primo pr = new Primo(Integer.parseInt(getName()));
int valor = pr.numero;
if (pr.es_primo_circular()){
lista_salida.add(valor);
System.out.println("Primo Circular: "+valor);
}
}

/* Metodo principal */
public static void main (String [] args) throws InterruptedException {
int numero_evaluado = 1000001;
for(int i=2;i<numero_evaluado;i++){
new MyThread(Integer.toString(i)).start();
Thread.sleep(1);
}
Thread.sleep(2000);
System.out.println("Cantidad de Primos Circulares Menores a "+numero_evaluado+": " + lista_salida.size());
}
}


Gracias!

[Xerelo]

La verdad es que es un ejercicio un poco raro, no acabo de ver muy claro que sea un ejercicio adecuado para hilos pero en fin, seguro que tu profesor tiene en mente algo que yo ahora mismo no veo.

Lo que se me ocurre es lo siguiente:

1. Los números pares no pueden ser primos, avanza de dos en dos a partir del uno y reducirás a la mitad los números.

2. En relación con el anterior, cualquier número que contenga un dígito par no podrá ser primo circular por el punto 1. Te ahorras unas cuantas comprobaciones de si un número es primo. Usa regex para detectarlos.

3. Dejaría el for (con el +2) y cada número primo sin dígito par lanza un hilo donde comprueba si es primo y sus circulares, si lo son los añades a un List, pero ojo los ArrayList no son thread-safe, tal como lo tienes puede dar algún error. Usa synchronized, Vector o algún tipo de listado thread-safe.

4. Cada número que vayas a comprobar, mira primero que no esté ya en la lista de primos circulares.

[Profesor_Falken]

Buenas,

Hace poco se posteó aquí una duda similar respecto al número de threads.
http://www.forosdelweb.com/f45/canti...iempo-1111410/

Te copio aquí la respuesta:

"

Buenas,

Cada vez que creas un thread, esto tiene un importante coste a nivel de recursos, ya que cada thread tiene su propio heap y stack de ejecucion. Por eso se te queda sin memoria.

Por otro lado lo que intentas es muy ineficiente, ya que el numero de cores de tu maquina es limitado. Ten en cuenta que cuando ejecutas muchos threads sobre un mismo core, este tiene que estar cambiando de contexto constantemente (http://es.wikipedia.org/wiki/Cambio_de_contexto)

El uso de muchos threads esta bien cuando se quieren ejecutar muchas tareas concurrentes sin dejar bloqueado al usuario. Por ejemplo un servidor, si no utilizase hilos, solo podria procesar una peticion al mismo tiempo.

Sin embargo tu caso es distinto, ya que no quieres ejecutar muchas tareas sino dividir una sola muy pesada. Esta es la diferencia entre concurrencia y paralelismo.

Lo que deberias hacer para conseguir el mayor rendimiento posible es basarte en el numero de cores de tu maquina:

Código Java:

int cores = Runtime.getRuntime().availableProcessors();
 

Ese es el numero de thread optimo para tu calculo.

Por otro lado, debes dividir bien las tareas. No puedes asignar a cada thread de forma secuencial.
Por ejemplo si tienes 4 cores y haces esto:
Thread 1: de 1 a 250000
Thread 2: de 250001 a 500000
[...]
Es muy mala idea ya que el algoritmo de calculo de primos es de complejidad lineal (O(n)) y por tanto, a mayor valor de n mas va a tardar. Lo mejor es que vayas asignando a cada core pequenos packs a procesar y segun vayan terminando le asignas nuevos hasta terminar.

"

En el otro caso puse un ejemplo para resolverlo con lambdas.

Otra forma correcta de hacerlo sería con Executors:
http://docs.oracle.com/javase/7/docs.../Executor.html

Sin embargo, como te piden threads, te he hecho una solucion siguiendo lo que decia más arriba.
Como no has puesto todo el código y hay cosas que no compilan lo he escrito sobre la marcha, por lo que puede haber algun error, incluso de compilación, pero supongo que no te costará corregirlo.

Puedes jugar con la variable BLOQUE para conseguir el rendimiento máximo. Dependerá del número evaluado: a mayor número, mayor debería ser el tamaño del bloque.

Código Java:

public class MyThread extends Thread {
 
    private static final int NUMERO_EVALUADO = 1000000;
 
    static List<Integer> lista_salida = new ArrayList<Integer>(NUMERO_EVALUADO);
 
    private static final int MAX_THREADS = Runtime.getRuntime().availableProcessors();
 
    private static final int BLOQUE = 200;
 
    private final List<Integer> startNums = new ArrayList<>();
 
    /* Constructor de la clase */
    public MyThread(String name) {
        super(name);
    }
 
    public void addStartNum(int startNum) {
        this.startNums.add(startNum);
    }
 
    /* Muestra por pantalla los elementos de una lista */
    private static void mostrar_lista_elementos(List elementos) {
        int i = 0;
        while (i < elementos.size()) {
            System.out.println(elementos.get(i));
            i++;
        }
    }
 
    /* Codigo a ser ejecutado por Threads */
    public void run() {
        for (final Integer startNum : startNums) {
            for (int i = startNum; i <= startNum + BLOQUE; i++) {
                Primo pr = new Primo(Integer.parseInt(getName()));
                int valor = pr.numero;
                if (pr.es_primo_circular()) {
                    lista_salida.add(valor);
                }
            }
        }
    }
 
    /* Metodo principal */
    public static void main(String[] args) throws InterruptedException {
 
        System.out.println("Evaluando " + NUMERO_EVALUADO + " con " + MAX_THREADS + " threads");
 
        //Inicializa el pool de threads
        MyThread[] threadPool = new MyThread[MAX_THREADS];
        for (int i = 0; i < threadPool.length; i++) {
            threadPool[i] = new MyThread("Thread-" + i);
        }
 
        //Asigna porciones de valores a cada thread
        int j = 0;
        for (int i = 0; i < NUMERO_EVALUADO; i += BLOQUE) {
            threadPool[j++].addStartNum(i);
            if (j >= MAX_THREADS) {
                j = 0;
            }
        }
 
        //Lanza todos los theads
        for (int i = 0; i < threadPool.length; i++) {
            threadPool[i].start();
        }
 
        //Espera que terminen todos los threads antes de terminar el principal
        for (int i = 0; i < threadPool.length; i++) {
            threadPool[i].join();
        }
 
        System.out.println("Cantidad de Primos Circulares Menores a " + NUMERO_EVALUADO + ": " + lista_salida.size());
    }
}
 

Los inconvenientes son que la lista probablemente esté desordenada y también, como bien comenta Xerelo, puede que haya problemas al insertar en el ArrayList, ya que no está sincronizarlo. Si lo tienes, basta con que hagas:

Código Java:

synchronized(lista_salida){
   lista_salida.add(valor);
}
 

Si no tienes problemas, mejor no sincronices, ya que tiene un alto coste en rendimiento.

Un saludo

[Xerelo]

Me acabo de dar cuenta, tampoco serán primos circulares los que contengan un 5 o 0.

Así que al final sólo tienes que preocuparte de los número formados por 1,3,7,9. Creo que se reducen tanto las posibilidades que casi ni merece la pena los hilos