Free Web Site - Free Web Space and Site Hosting - Web Hosting - Internet Store and Ecommerce Solution Provider - High Speed Internet
Search the Web

Números primos

Como definición, un número primo es el que sólo es divisible por sí mismo y por 1.
Ej : 1 , 2 , 3 , 5 , 7 , 11 , 13 ...

La dificultad es determinar si un número "grande" es primo o no. Por ejemplo ¿como sabemos de buenas a primeras si 2567 es primo? . Para ello es que se han creado variados algoritmos que determinan la respuesta con cierta eficiencia.

Un algoritmo básico es el ir contando cuántos divisores válidos se encuentran para un número de entrada.
En general los números primos sólo tendrían dos divisores, a excepción del 1 que obviamente tiene un divisor. Para ello mediante un ciclo iterativo se van realizando las divisiones y contando con una variable entera.

Algoritmo

Leer num
contador = 0
i = 1
mientras ( i <= num) hacer
    si (RESTO(num / i) == 0) entonces 
        contador = contador + 1  
    fin si
    i = i  + 1 
fin mientras 

si (contador < = 2) entonces
    num es primo
sino
    num no es primo
fin si

Ahora para pasar este algoritmo a Java, incorporamos una variable de tipo boolean para que un método retorne true o false. El método sería el siguiente :

class prbprimo1
{
    public static void main(String arg[])
    {
        for(int i = 1; i <= 25000; i++ )
               if (primo(i) == true) System.out.println(i);    
    }

    public static boolean primo(int num)
    {
        boolean p;
        int contador = 0;
        int i = 1;
        while(i <= num)  
        {
            if (num  % i == 0)  contador++; 
            i++;
        }
    
        if (contador <= 2) p = true;
        else p = false;

        return p;
    }
}

Mejorando un poco lo anterior, uno se da cuenta que sólo basta que el contador sea mayor que 2 para salir del ciclo while. Esto sin duda reduce el tiempo de ejecución para los números grandes que no sean primos, ya que con una mínima cantidad de ciclos se determina el resultado.
Además podemos inicializar la variable p en false, suponiendo que el número no es primo.

class prbprimo2
{
    public static void main(String arg[])
    {
        for(int i = 1; i <= 25000; i++ )
               if (primo(i) == true) System.out.println(i);    
    }

    public static boolean primo(int num)
    {
        boolean p = false;
        int contador = 0;
        int i = 1;
        
        while(i <= num)  
        {
            if (num  % i == 0) contador++; 
            i++;  
            if (contador > 2) i =  num  + 1; 
        }
    
        if (contador <= 2) p = true;
    
        return p;
    }
}

Con la instrucción : if (contador > 2) i = num + 1; forzamos la salida del ciclo, logrando el resultado esperado.

Ahora, notemos que todos los números pares (menos el 2) no son primos. Además tenemos 3 números consecutivos que son primos : 1,2,3.
Para una rápida revisión de estos números incorporamos la instrucción :

if(num < 4) p = true;

y de alguna manera no permitimos que se entre en el ciclo.
Además podemos deducir que todos los pares mayores que 2 no son primos. Esto nos llevaría a un algoritmo como el siguiente :

Leer num
contador = 0  

si(num <  4) entonces
    num es primo
sino
   si (RESTO(num / 2) == 0) entonces
       num no es primo
   sino
       comprobar para los impares mayores que 3
   fin si
fin si 

class prbprimo3
{
    public static void main(String arg[])
    {
        for(int i = 1; i <= 25000; i++ )
               if (primo(i) == true) System.out.println(i);    
    }

    public static boolean primo(int num)
    {
        boolean p = false;
    
        if (num < 4) p = true;
        else
        {
            if (num % 2 == 0) p = false; 
            else
            {
                int contador = 0;  
                int i = 1;  
                while(i <= num)  
                {
                    if (num  % i == 0) contador++; 
                    i++;  
                    if (contador > 2) i =  num  + 1; 
                }
            
                if (contador <= 2) p = true;
            } 
        } 
    
        return p;
    }

}

Como los números primos son impares , es inútil dividir num por un número par. Por lo tanto sólo se admiten divisores impares. El problema es reducir el número de ciclos para los impares no primos.

num : {divisores válidos}

15 : {1,3,5,7,9,11,13,15}
21 : {1,3,5,7,9,11,13,15,17,19,21}
25 : {1,3,5,7,9,11,13,15,17,19,21,23,25}
27 : {1,3,5,7,9,11,13,15,17,19,21,23,25,27}

Ahora veremos cuales son los divisores donde se produce el resto igual a cero

15 : {1,3,5,7,9,11,13,15}
21 : {1,3,5,7,9,11,13,15,17,19,21}
25 : {1,3,5,7,9,11,13,15,17,19,21,23,25}
27 : {1,3,5,7,9,11,13,15,17,19,21,23,25,27}
33 : {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33}

Si se omite como divisor el mismo número y los divisores mayores que
(num - 1) / 2) se tiene :

15 --> (15 - 1) / 2) = 7
21 --> (21 - 1) / 2) = 10
25 --> (25 - 1) / 2) = 12
27 --> (27 - 1) / 2) = 13
33 --> (33 - 1) / 2)= 16

15 : {1,3,5,7}
21 : {1,3,5,7,9}
25 : {1,3,5,7,9,11}
27 : {1,3,5,7,9,11,13}
33 : {1,3,5,7,9,11,13,15}

Comprobando para los primos mayores que 3 :

5 : {1}
7 : {1,3}
11 : {1,3,5}


Para determinar el último divisor válido aplicamos el siguiente algoritmo :

limite = (num - 1) / 2
si (RESTO(limite /  2) == 0) 
    limite = limite - 1
fin si

Tomando en cuenta que ahora se necesita que el contador tome el valor 1 se tiene el siguiente método :

class prbprimo4
{
    public static void main(String arg[])
    {
        for(int i = 1; i <= 25000; i++ )
               if (primo(i) == true) System.out.println(i);    
    }

    public static boolean primo(int num)
    {
        boolean p = false;
    
        if (num < 4) p = true;
        else
        {
            if (num % 2 == 0) p = false; 
            else
            {
                int contador = 0;  
                int i = 1; 
                int limite = (num - 1) / 2; 
                if  (limite % 2 == 0) limite--;  
            
                while(i <= limite)
                {
                    if (num % i == 0) contador++;
                    i += 2;
                    if (contador == 2) i = limite + 1;
                }

                if (contador == 1) p = true;
            } 
        } 
    
        return p;
    }

}

Al medir los tiempos aproximados de ejecución de cada clase, se obtuvieron los siguientes resultados (Procesador : Intel Celeron 800 MHz )