Trovare i numeri primi con il Crivello di Eratostene (Originariamente:C'è un modo migliore per preparare questo array?)

Question

Nota: Versione 2, di seguito, utilizza il Crivello di Eratostene.Ci sono diverse risposte che hanno contribuito con quello che ho inizialmente chiesto.Ho scelto il Crivello di Eratostene metodo implementato e modificato il titolo della domanda e tag in modo appropriato.Grazie a tutti coloro che hanno contribuito!

Introduzione

Per questo ho scritto un po ' di fantasia metodo che genera un array di int che contiene i numeri primi inferiore al limite specificato.Funziona molto bene, ma ho un problema.

Il Metodo

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;
}

La Mia Preoccupazione

La mia preoccupazione è che sto creando una matrice che è troppo grande per il numero di elementi, il metodo restituirà.Il guaio è che non so un buon modo per indovinare il numero di numeri primi inferiori a un numero specificato.

Focus

Questo è come il programma utilizza le matrici.Questo è quello che voglio migliorare.

1. Ho creato un array temporaneo che è grande abbastanza per contenere ogni numero inferiore a tale limite.
2. Generare numeri primi, mentre tenere un conteggio di quanti ne ho generata.
3. Devo creare un nuovo array che è il diritto dimensione di tenere solo il primo numeri.
4. Ho la copia di ogni numero primo da enorme array di array di dimensione corretta.
5. Mi restituisce l'array di corretta dimensione che contiene solo il primo numeri che ti ho generato.

Domande

1. Posso copiare l'intero pezzo (contemporaneamente) di temp[] che è diverso da zero elementi di primes[] senza dover scorrere entrambe le matrici e copiare gli elementi uno per uno?
2. Ci sono strutture di dati che comportarsi come un array di tipi primitivi in grado di crescere con l'aggiunta di elementi, piuttosto che avere una dimensione durante la creazione di istanze?Qual è il pena di prestazioni rispetto a utilizzando un array di tipi primitivi?

---

Versione 2 (grazie 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);
}

---

Versione 3 (grazie a Paolo Tomblin) che utilizza il Setaccio di Erastosthenes:

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

Il tuo metodo di ricerca di numeri primi, confrontando ogni singolo elemento della matrice di ogni possibile fattore è terribilmente inefficiente. È possibile migliorare immensamente facendo una Crivello di Eratostene sull'intera matrice in una sola volta. Oltre a fare molti meno confronti, utilizza anche oltre, piuttosto che di divisione. Divisione è il modo più lento.

Answer 2

ArrayList<> Crivello di Eratostene

// 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;
}

Formula per limite superiore del numero dei primi minori o uguali a max (vedi wolfram.com ):

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

Answer 3

Crea un ArrayList<Integer> e poi convertire in un int[] alla fine.

Ci sono vari IntList 3rd party (ecc) classi in giro, ma se non sei davvero preoccupati per il colpo di boxe alcuni interi, io non ti preoccupare.

Si potrebbe utilizzare Arrays.copyOf per creare il nuovo array però. Si potrebbe anche voler ridimensionare raddoppiando in termini di dimensioni ogni volta che è necessario, e poi ritagliare alla fine. Questo sarebbe fondamentalmente imitando il comportamento ArrayList.

Answer 4

Algo utilizzando Crivello di Eratostene

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;
}

Immagine raffigurante l'algo sopra (celle di colore grigio rappresentano numero primo. Poiché consideriamo tutti i numeri come numeri primi intially, il tutto è griglia è grigio inizialmente.)

Immagine Fonte: WikiMedia

Answer 5

La soluzione più semplice sarebbe quella di tornare un membro del quadro Collezioni invece che una matrice.

Answer 6

Stai usando Java 1.5? Perché non tornare List<Integer> e utilizzare ArrayList<Integer>? Se si ha bisogno di restituire un int[], è possibile farlo convertendo List per int[] alla fine del trattamento.

Answer 7

Come Paolo Tomblin fa notare, ci sono gli algoritmi migliori.

Ma mantenere con quello che hai, e supponendo un oggetto per ogni risultato è troppo grande:

Si sono sempre e solo ad appendere alla matrice. Quindi, utilizzare una parte relativamente piccola serie int []. Quando è pieno uso aggiungerla a una lista e creare una sostituzione. Alla fine copia in una matrice di dimensioni corrette.

In alternativa, indovinare la dimensione del int [] array. Se è troppo piccola, sostituire con un int [] con una dimensione una frazione maggiore della dimensione dell'array corrente. L'overhead prestazioni di questo resterà proporzionale alla dimensione. (Questo è stato brevemente discusso in un recente podcast di StackOverflow.)

Answer 8

Ora che hai un setaccio di base sul posto, si noti che il ciclo interno deve continuare solo fino temp[i]*temp[i] > prime.

Answer 9

Ho un applicazione davvero efficace:

1. non teniamo i numeri pari, pertanto, dimezzando l'utilizzo della memoria.
2. usiamo BitSet, che richiede solo un bit per numero.
3. si stima il limite superiore per il numero di primi sull'intervallo, così possiamo impostare la initialCapacity per l'array appropriato.
4. noi non eseguire alcun tipo di divisione nei cicli.

Ecco il codice:

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

Ristruttura il codice. Gettare l'array temporaneo, e invece scrivere funzione che appena prime-test un numero intero. Sarà ragionevolmente veloce, dal momento che si sta utilizzando solo tipi nativi. Quindi è possibile, ad esempio, loop e costruire una lista di numeri interi che sono primi, prima infine conversione che ad un array di tornare.

Answer 11

Finalmente ho finito il programma È ottimizzato sieve

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

Non sono sicuro se questo sarà internet a vostra situazione, ma è possibile dare un'occhiata al mio approccio. Ho usato il mio utilizzando Crivello di Eratostene .

  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;
    }

Commento aggiunto per ogni passi che è stato illustrato in Wikipedia

Answer 13

L'ho fatto usando HashMap e l'ho trovato molto semplice

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);
                    }
                }

            }
        }

    }

}

Credo che questo è efficace

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;
            }
        }
    }