java - metodo - numeros primos del 1 al 100

Encontrar números primos con el Tamiz de Eratóstenes(Originalmente: ¿Hay una mejor manera de preparar esta matriz?)

Question

Nota: La versión 2, a continuación, utiliza el Tamiz de Eratóstenes. Hay varias respuestas que ayudaron con lo que originalmente pregunté. Elegí el método del Tamiz de Eratóstenes, lo implementé y cambié el título de la pregunta y las etiquetas de manera apropiada. Gracias a todos los que ayudaron!

Introducción

Escribí este pequeño método sofisticado que genera una matriz de int que contiene los números primos menos que el límite superior especificado. Funciona muy bien, pero tengo una preocupación.

El método

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    int [] primes = new int [index];
    while(--index >= 0) {
        primes [index] = temp [index];
    }
    return primes;
}

Mi preocupación

Mi preocupación es que estoy creando una matriz que es demasiado grande para el número final de elementos que devolverá el método. El problema es que no conozco una buena manera de adivinar correctamente el número de números primos menos que un número especificado.

Atención

Así es como el programa utiliza las matrices. Esto es lo que quiero mejorar.

1. Creo una matriz temporal que es lo suficientemente grande como para contener cada número por debajo del límite.
2. Genero los números primos, mientras cuento cuántos he generado.
3. Hago una nueva matriz que es la dimensión correcta para mantener solo los números primos.
4. Copio cada número primo de la enorme matriz a la matriz de la dimensión correcta.
5. Devuelvo la matriz de la dimensión correcta que contiene solo los números primos que generé.

Preguntas

1. ¿Puedo copiar todo el fragmento (a la vez) de temp[] que tiene elementos distintos de cero en primes[] sin tener que iterar a través de ambas matrices y copiar los elementos uno por uno?
2. ¿Hay estructuras de datos que se comportan como una matriz de primitivas que pueden crecer a medida que se agregan elementos, en lugar de requerir una dimensión en la instanciación? ¿Cuál es la penalización de rendimiento en comparación con el uso de una matriz de primitivas?

Versión 2 (gracias a Jon Skeet ):

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    return Arrays.copyOfRange(temp, 0, index);
}

Versión 3 (gracias a Paul Tomblin ) que usa el Tamiz de Erastóstenes :

private static int [] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) {
        if (!isComposite [i]) {
            for (int j = i; i * j <= max; j++) {
                isComposite [i*j] = true;
            }
        }
    }
    int numPrimes = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) numPrimes++;
    }
    int [] primes = new int [numPrimes];
    int index = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) primes [index++] = i;
    }
    return primes;
}

Answer 1

ArrayList<> Tamiz de Eratóstenes

// Return primes less than limit
static ArrayList<Integer> generatePrimes(int limit) {
    final int numPrimes = countPrimesUpperBound(limit);
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    boolean [] isComposite    = new boolean [limit];   // all false
    final int sqrtLimit       = (int)Math.sqrt(limit); // floor
    for (int i = 2; i <= sqrtLimit; i++) {
        if (!isComposite [i]) {
            primes.add(i);
            for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
                isComposite [j] = true;
        }
    }
    for (int i = sqrtLimit + 1; i < limit; i++)
        if (!isComposite [i])
            primes.add(i);
    return primes;
}

Fórmula para el límite superior del número de primos menor o igual al max (consulte wolfram.com ):

static int countPrimesUpperBound(int max) {
    return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
}

Answer 2

¿Estás utilizando Java 1.5? ¿Por qué no devolver la List<Integer> y usar ArrayList<Integer> ? Si necesita devolver un int[] , puede hacerlo convirtiendo List a int[] al final del procesamiento.

Answer 3

Ahora que tiene un tamiz básico en su lugar, tenga en cuenta que el bucle interno solo debe continuar hasta que temp[i]*temp[i] > prime .

Answer 4

Algo utilizando Tamiz de Eratóstenes

public static List<Integer> findPrimes(int limit) {

    List<Integer> list = new ArrayList<>();

    boolean [] isComposite = new boolean [limit + 1]; // limit + 1 because we won''t use ''0''th index of the array
    isComposite[1] = true;

    // Mark all composite numbers
    for (int i = 2; i <= limit; i++) {
        if (!isComposite[i]) {
            // ''i'' is a prime number
            list.add(i);
            int multiple = 2;
            while (i * multiple <= limit) {
                isComposite [i * multiple] = true;
                multiple++;
            }
        }
    }

    return list;
}

Imagen que muestra el algo anterior (las celdas de color gris representan el número primo. Dado que consideramos todos los números como números primos inicialmente, la totalidad de la cuadrícula es gris inicialmente).

Fuente de la imagen: WikiMedia

Answer 5

Como señala Paul Tomblin, hay mejores algoritmos.

Pero mantener lo que tiene y asumir un objeto por resultado es demasiado grande:

Sólo estás agregando a la matriz. Por lo tanto, use una matriz int [] relativamente pequeña. Cuando sea de uso completo, agréguelo a una Lista y cree un reemplazo. Al final, cópielo en una matriz de tamaño correcto.

Alternativamente, adivine el tamaño de la matriz int []. Si es demasiado pequeño, sustitúyalo por un int [] con un tamaño una fracción mayor que el tamaño actual de la matriz. La sobrecarga de rendimiento de esto seguirá siendo proporcional al tamaño. (Esto fue discutido brevemente en un podcast reciente de ).

Answer 6

Cree un ArrayList<Integer> y luego conviértalo a un int[] al final.

Hay varias clases de IntList (etc.) de terceros, pero a menos que esté realmente preocupado por el éxito del boxeo con algunos enteros, no me preocuparía por eso.

Sin embargo, puede usar Arrays.copyOf para crear la nueva matriz. Es posible que también desee cambiar el tamaño duplicando el tamaño cada vez que lo necesite, y luego recorte al final. Básicamente, eso sería imitar el comportamiento de ArrayList .

Answer 7

Finalmente terminé el programa. Es un tamiz optimizado.

public static int[] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    LinkedList<Integer> Primes = new LinkedList<>(); //linkedlist so not have to iterate 2 times
    int sqrt = (int) Math.sqrt(max); //end at the square root
    for (int i = 2; i <= sqrt; i++) {
        if (!isComposite[i]) {
            int s = i*i; //start from the prime''s square
            while (s <= max) {
                isComposite[s] = true; //oh no its a not prime
                s+=i;
            }
        }
    }
    for(int i = 2; i < max; i++){
        if(!isComposite[i]){
            Primes.add(i);
        }
    }
    int[] result = new int[Primes.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = Primes.get(i);
    }
    return result;
}

Answer 8

He terminado de usar HashMap y lo encontré muy simple.

import java.util.HashMap;
import java.util.Map;

/*Using Algorithms such as sieve of Eratosthanas */

public class PrimeNumber {

    public static void main(String[] args) {

        int prime = 15;
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        hashMap.put(0, 0);
        hashMap.put(1, 0);
        for (int i = 2; i <= prime; i++) {

            hashMap.put(i, 1);// Assuming all numbers are prime
        }

        printPrimeNumberEratoshanas(hashMap, prime);

    }

    private static void printPrimeNumberEratoshanas(HashMap<Integer, Integer> hashMap, int prime) {

        System.out.println("Printing prime numbers upto" + prime + ".....");
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            if (entry.getValue().equals(1)) {
                System.out.println(entry.getKey());
                for (int j = entry.getKey(); j < prime; j++) {
                    for (int k = j; k * j <= prime; k++) {
                        hashMap.put(j * k, 0);
                    }
                }

            }
        }

    }

}

Creo que esto es efectivo

Answer 9

La solución más sencilla sería devolver algún miembro de Collections Framework en lugar de una matriz.

Answer 10

No estoy seguro de si esto se adaptará a tu situación pero puedes echar un vistazo a mi enfoque Utilicé la mía usando Tamiz de Eratóstenes .

  public static List<Integer> sieves(int n) {
        Map<Integer,Boolean> numbers = new LinkedHashMap<>();

        List<Integer> primes = new ArrayList<>();

        //First generate a list of integers from 2 to 30
        for(int i=2; i<n;i++){
            numbers.put(i,true);
        }

        for(int i : numbers.keySet()){
            /**
             * The first number in the list is 2; cross out every 2nd number in the list after 2 by 
             * counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):
             * 
             * The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by 
             * counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):
             * The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every
             * 7th number in the list after 7, but they are all already crossed out at this point,
             * as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. 
             * The numbers not crossed out at this point in the list are all the prime numbers below 30:
             */
            if(numbers.get(i)){
                for(int j = i+i; j<n; j+=i) {
                    numbers.put(j,false);
                }
            }
        }


        for(int i : numbers.keySet()){
            for(int j = i+i; j<n && numbers.get(i); j+=i) {
                numbers.put(j,false);
            }
        }

        for(int i : numbers.keySet()){
           if(numbers.get(i)) {
               primes.add(i);
           }
        }
        return primes;
    }

Comentario agregado para cada paso que se ha ilustrado en wikipedia

Answer 11

Reestructura tu código. Deseche la matriz temporal y, en su lugar, escriba una función que solo realice pruebas primarias de un entero. Será razonablemente rápido, ya que solo estás usando tipos nativos. Luego puede, por ejemplo, hacer un bucle y construir una lista de enteros que son primos, antes de convertirlos finalmente en una matriz para devolverlos.

Answer 12

Su método para encontrar números primos, al comparar cada elemento de la matriz con cada factor posible es horriblemente ineficiente. Puedes mejorarlo inmensamente haciendo un Tamiz de Eratóstenes sobre toda la matriz a la vez. Además de hacer muchas menos comparaciones, también usa la suma en lugar de la división. La división es mucho más lenta.

Answer 13

Tengo una implementación muy eficiente:

1. No mantenemos los números pares, por lo tanto, reducimos a la mitad el uso de la memoria.
2. usamos BitSet , que requiere solo un bit por número.
3. estimamos el límite superior para el número de primos en el intervalo, por lo que podemos establecer la initialCapacity para el Array de forma apropiada.
4. No realizamos ningún tipo de división en los bucles.

Aquí está el código:

public ArrayList<Integer> sieve(int n) {
    int upperBound = (int) (1.25506 * n / Math.log(n));
    ArrayList<Integer> result = new ArrayList<Integer>(upperBound);
    if (n >= 2)
        result.add(2);

    int size = (n - 1) / 2;
    BitSet bs = new BitSet(size);

    int i = 0;
    while (i < size) {
        int p = 3 + 2 * i;
        result.add(p);

        for (int j = i + p; j < size; j += p)
            bs.set(j);

        i = bs.nextClearBit(i + 1);
    }

    return result;
}