jueves, octubre 21, 2010

Números Primos

Verificación

Teniendo en cuenta que, por definición, un número primo es aquel que es divisible exclusivamente por sí mismo y por la unidad, se puede escribir una función que verifique si un número entero es primo dividiéndolo por todos los números entre 1 y él, y finalmente contar cuántos divisores tuvo. Si la cantidad de divisores es 2, entonces el número es primo, de lo contrario no lo es. Este algoritmo se puede representar como:

// Version inicial.  Cuenta el numero de divisores y si es menor o igual
// que dos entonces es primo.
    public static boolean esPrimoV1(long n) {
        long contador=0;
        for(long i=1; i<=n; i++) {
            if(n%i == 0) contador  ;
        }
        if(contador>=2) return false;
        else return true;
    }

Este algoritmo, si bien identifica si el número es primo, es bastante ineficiente, entre otras por razones tales como la espera para hacer todas las divisiones para decidir que un número no es primo aunque, si se omite la división por uno y por el mismo número, basta con encontrar un solo divisor más para determinar que el número no es primo. De la misma manera, el algoritmo divide el número por todos los pares anteriores a él cuando no es necesario, ya que diviéndolo por dos es suficiente para saber si es múltiplo de un número par.

Una versión optimizada del algoritmo es la siguiente:

// Version seis.  Hace los cálculos de funciones solo cuando es necesario
    public static boolean esPrimoV6(long n) {
        double raiz = Math.sqrt(n);
        if(n==2) return true;
        if(n%2==0) return false;
        for(long i=3; i<=raiz; i+=2) {
            if(n%i == 0) return false;
        }
        return true;
    }

Se sugiere calcular con las dos versiones el tiempo que se tarda en determinar si el número entero más grande que puede manejar java (Long.MAX_VALUE) es primo o no.

Generación

Si se quiere generar un conjunto de números primos, una posible alternativa es utilizar el método de Eratóstenes, en el cual se ubican en un vector todos los posibles números en un rango, e iniciando en el número 2 se marcan como no primos todos los múltiplos de dicho número; el proceso continua para todos los números no marcados.

El siguiente método genera un vector con todos los números enteros entre 1 y 2 a la 31:

// Generación de primos por el método de Eratóstenes
    public static int[] generarPrimos() {
        boolean[] tmp = new boolean[Integer.MAX_VALUE/2];
        for(int i=0; i<tmp.length; i++) tmp[i]=true;
        int contador  = tmp.length;
        int raiz      = (int) Math.sqrt(tmp.length);
        for(int i=2; i<=raiz; i++) {
            if(tmp[i]!=true) continue;
            for(int j=i*i; j<tmp.length;j+=i){
                if(tmp[j]==true) {
                    contador--;
                    tmp[j]=false;
                }
            }
        }
        int   j         = 0;
        int[] respuesta = new int[contador];
        for(int i=0; i<tmp.length; i++) if(tmp[i]==true) respuesta[j++]=i;
        return respuesta;
    }

Nótese que el arreglo tmp podría usarse para determinar de forma inmediata si un número dado es primo o no, pues bastaría con mirar si la posición respectiva de ese número en el arreglo hay un valor de falso o verdadero.

1 comentario:

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...