IMPLEMENTACIÓN DE LA CRIBA DE ERASTOTENES EN JAVA

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado n. Se forma una tabla con todos los números naturales comprendidos entre 2 y n, y se van tachando los números que no son primos de la siguiente manera:

• Hallamos la raíz cuadrada de n(rc).
• Obtenemos los primos menores a la raíz cuadrada de n(rc).
• Se presenta gráficamente el proceso de Erastotenes  aplicado a cada uno de los primos menores a rc.Se marca todos los múltiplos mayores a cada primo menor que rc.
• Después  de marcar , todos los números que quedan diferentes de 1 serán los números primos existentes entre 2 y n.

Ejemplo: Aplicar la criba de Erastotenes para los primeros 100 números naturales.

Paso 1: Raíz cuadrada de 100 = 10

Paso 2: Primos menos que 10= {2,3,5,7}

Paso 3: 

Paso 4: Listar números primos de 2 a N: 

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

IMPLEMENTACIÓN EN JAVA:

public ArrayList< Integer > CribaE()
    {
        ArrayList< Integer > aux_primos = new ArrayList<>();
        ArrayList< Integer > listade2aN = new ArrayList<>();
        int aux,i=3;
        aux=(int) Math.sqrt(numero);//SACANDO LA RAIZ CUADRADA DE N
        aux_primos.add(2);//PRIMER ELEMENTO DEL ARRAY AUXLIAR D EPRIMOS QUE SERVIRAM PARA APLICAR LA CRIBA
        int contador=0;
        while(i< aux)
        {
            if(aux_primos.size()==1)
            {
                aux_primos.add(i);
            }
            else
            {
                for(int k=0;k < aux_primos.size();k++)
                {
                    if(i%aux_primos.get(k)==0)
                    {
                        contador++;
                    }
                }
                if(contador==0)
                {
                    aux_primos.add(i);//AGREGANDO A LA LISTA AUXLIAR TODOS LOS PRMOS MENORES QUE LA RAIZ CUADRADA
                }
            }
            i=i+2;
            contador=0;
        }
        for(int j=0;j < (numero);j++)
        {
            listade2aN.add(j+1);
        }
        for(int m=0;m< aux_primos.size();m++)
        {
            for(int h=0;h< listade2aN.size();h++)
            {
                if(listade2aN.get(h)==1)
                {
                    listade2aN.remove(h);//PARA ELIMINAR EL 1
                }
                if((listade2aN.get(h)%aux_primos.get(m)==0)&&(listade2aN.get(h)!=aux_primos.get(m)))
                {
                    listade2aN.remove(h);//ELIMINANDO A LOS MULTIPLOS DE LOS PRIMOS MENORES A LA RAIZ DE N
                }
            }
        }
        return listade2aN;
    }

• Tweet
• Share
• Share
• Share
• Share