Encontrar números primos con el Tamiz de Eratóstenes (Originalmente:¿Existe 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 pregunté originalmente.Elegí el método Tamiz de Eratóstenes, lo implementé y cambié el título de la pregunta y las etiquetas de manera adecuada.¡Gracias a todos los que ayudaron!

Introducción

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

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 la cantidad 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 menores que un número específico.

Enfocar

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

1. Creo una matriz temporal que es lo suficientemente grande como para contener cada número menos que el límite.
2. Generizo los números primos, mientras mantengo la cuenta de cuántos he generado.
3. Hago una nueva matriz que es la dimensión correcta para contener solo los números primos.
4. Copio cada número primo de la gran matriz a la matriz de la dimensión correcta.
5. Devuelve la matriz de la dimensión correcta que contiene solo los números primos que generé.

Preguntas

1. ¿Puedo copiar todo el fragmento (de una vez) detemp[] que tiene elementos distintos de cero para primes[]¿Sin tener que iterar a través de ambas matrices y copiar los elementos uno por uno?
2. ¿Hay alguna estructura de datos que se comporte como una variedad de primitivas que pueden crecer a medida que se agregan elementos, en lugar de requerir una dimensión al instanciar?¿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 Pablo Tomblin) que utiliza 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

Su método de búsqueda de números primos, mediante la comparación de cada elemento de la matriz con cada posible factor es terriblemente ineficiente. Usted puede mejorar enormemente haciendo una criba de Eratóstenes lo largo de toda la matriz a la vez. Además de hacer muchas menos comparaciones, sino que también utiliza además en lugar de la división. División es la forma más lenta.

Answer 2

ArrayList<> criba 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 límite superior de número de primos menores o iguales a max (ver wolfram.com ):

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

Answer 3

Crear una ArrayList<Integer> y luego convertir a un int[] al final.

Hay varias clases IntList tercera parte (etc) alrededor, pero a menos que seas realmente preocupado por el golpe de boxeo unos números enteros, yo no preocuparse por ello.

Se puede usar Arrays.copyOf para crear la nueva matriz sin embargo. También puede ser que desee cambiar el tamaño, duplicando su tamaño cada vez que necesite, y luego cortar al final. Que básicamente sería que imitan el comportamiento ArrayList.

Answer 4

Algo usando criba 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 representa el algo más arriba (células de color gris representan los números primos. Puesto que se considera que todos los números de los números primos inicialmente, el todo es rejilla es de color gris inicialmente.)

Fuente de la imagen: WikiMedia

Answer 5

La solución más fácil sería volver algún miembro del Marco Colecciones lugar de una matriz.

Answer 6

¿Está utilizando Java 1.5? ¿Por qué no volver List<Integer> y utilizar ArrayList<Integer>? Si es necesario devolver un int[], puede hacerlo mediante la conversión Lista de int[] al final del proceso.

Answer 7

Como Pablo Tomblin señala, hay mejores algoritmos.

Sin embargo, mantener con lo que tienes, y asumiendo un objeto por resultado es demasiado grande:

Está solamente siempre realizando adiciones a la matriz. Por lo tanto, utilizar un relativamente pequeño int array []. Cuando sea el pleno uso anexar a una lista y crear un reemplazo. Al final copiarlo en una matriz de tamaño correcto.

Alternativamente, adivinar el tamaño de la matriz int []. Si es demasiado pequeña, reemplace por un int [] con un tamaño de una fracción más grande que el tamaño de la matriz actual. La sobrecarga de rendimiento de esta permanecerá proporcional al tamaño. (Esto fue discutido brevemente en un podcast stackoverflow reciente.)

Answer 8

Ahora que tienes un tamiz básica en su lugar, tenga en cuenta que el bucle interior sólo tiene que continuar hasta que temp[i]*temp[i] > prime.

Answer 9

Tengo una aplicación muy eficiente:

1. no mantenemos los números pares, por lo tanto, reducir a la mitad el uso de memoria.
2. utilizamos BitSet, que requiere sólo un bit por cada número.
3. Estimamos que el límite superior para el número de números primos en el intervalo, por tanto, podemos establecer la initialCapacity para la matriz de forma apropiada.
4. No realiza 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;
}

Answer 10

reestructurar su código. Tire a la basura la matriz temporal, y la función que acaba de prime-prueba un número entero en lugar de escribir. Será razonablemente rápido, ya que sólo está utilizando tipos nativos. A continuación, se puede, por ejemplo, bucle y crear una lista de números enteros y primos, antes de que finalmente la conversión que a una matriz para volver.

Answer 11

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 12

No estoy seguro de si esto se adaptará a su situación, pero puede consultar mi enfoque.Yo usé el mío 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;
    }

Se agregó un comentario para cada paso que se ha ilustrado en Wikipedia.

Answer 13

he hecho usando HashMap y lo encontramos muy sencilla

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 eficaz

Answer 14

public static void primes(int n) {
        boolean[] lista = new boolean[n+1];
        for (int i=2;i<lista.length;i++) {
            if (lista[i]==false) {
                System.out.print(i + " ");
            }
            for (int j=i+i;j<lista.length;j+=i) {
                lista[j]=true;
            }
        }
    }