Números Primos en Groovy

En este programa se genera una lista de 10 números primeros utilizando el lenguaje Groovy. Es importante recordar que Groovy es un lenguaje de desarrollo rápido que utiliza la funcionalidad y genera código que corre sobre la máquina virtual de java (Información en wikipedia)

def esPrimo = {
    n -> if(n==2) return true
    if(n%2==0) return false
    raiz = Math.sqrt(n)
    for(i=3; i<=raiz; i+=2) if(n%i==0) return false
    return true
}
Random rnd = new Random()
listaPrimos = []
while(listaPrimos.size < 10) {
    numero = rnd.nextInt(1000000)
    if(esPrimo(numero)) listaPrimos.add numero
}
println listaPrimos

El programa muestra varias cosas interesantes sobre la funcionalidad de groovy como son las siguientes:
- No se definen clases pues el objetivo del programa no implica la creación de objetos
- No se requieren los punto y comas (;) al final de cada instrucción
- No se deben declarar las variables
- Existe el tipo de datos lista, que internamente se forma a partir de un LinkedList
- No se debe importar el paquete java.util
- Los métodos no se deben declarar ni en su valor de retorno ni en los parámetros que reciben

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.