Trouver des nombres premiers avec le Crible d'Eratosthène (origine: Y at-il une meilleure façon de préparer ce tableau?)

Question

Remarque: Version 2, ci-dessous, utilise le Crible d'Eratosthène. Il y a plusieurs réponses qui ont contribué à ce que je initialement demandé. J'ai choisi la méthode d'Eratosthène Sieve, mis en œuvre, et changé le titre de la question et les balises de façon appropriée. Merci à tous ceux qui ont aidé!

Introduction

I écrit cette petite méthode de fantaisie qui génère un tableau d'int contenant les nombres premiers inférieure à la limite supérieure spécifiée. Il fonctionne très bien, mais je crains.

La méthode

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

Ma préoccupation

Mon souci est que je crée un tableau qui est beaucoup trop grand pour le nombre final d'éléments de la méthode retourne. Le problème est que je ne sais pas d'une bonne façon de deviner correctement le nombre de nombres premiers inférieur à un nombre spécifié.

Focus

Voici comment le programme utilise les tableaux. Voilà ce que je veux améliorer.

1. créer un tableau temporaire qui est assez grand pour contenir tous les numéros inférieure à la limite.
2. Je produis les nombres premiers, alors que en comptant le nombre de combien je généré.
3. Je fais un nouveau tableau qui est le droit dimension à tenir juste le premier numéros.
4. copier chaque numéro du premier énorme tableau au tableau du dimension correcte.
5. Je retourne le tableau de la bonne dimension qui ne détient que le premier numéros I générés.

Questions

1. Puis-je copier tout le morceau (à la fois) de temp[] qui a non nul éléments à primes[] sans avoir à effectuer une itération dans les deux matrices et copier les éléments un par un?
2. Y a-t-il des structures de données se comporter comme un tableau de primitives qui peut se développer comme des éléments sont ajoutés, plutôt que d'exiger une dimension à l'instanciation? Quel est le pénalité de performance par rapport à en utilisant un tableau de primitives?

---

Version 2 (grâce à 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);
}

---

La version 3 (grâce à Paul Tomblin ) qui utilise le crible d'Ératosthène :

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

Votre méthode de trouver des nombres premiers, en comparant chaque élément du tableau avec tous les facteurs possibles est affreusement inefficace. Vous pouvez l'améliorer énormément en faisant une d'Eratosthène Sieve sur l'ensemble du réseau à la fois. En plus de faire des comparaisons beaucoup moins, il utilise également l'addition plutôt que la division. Division est beaucoup plus lente.

Answer 2

ArrayList<> Sieve d'Eratosthène

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

Formule de limite supérieure du nombre de nombres premiers inférieurs ou égaux à max (voir wolfram.com ):

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

Answer 3

Créer un ArrayList<Integer> puis convertir en un int[] à la fin.

Il existe différents IntList 3ème partie (etc.) des classes autour, mais à moins que vous êtes vraiment inquiet au sujet du succès de la boxe quelques entiers, je ne vous inquiétez pas.

Vous pouvez utiliser Arrays.copyOf pour créer le nouveau tableau cependant. Vous pouvez également redimensionner en doublant la taille chaque fois que vous devez, puis couper à la fin. Ce serait essentiellement mimer le comportement de ArrayList.

Answer 4

Algo à l'aide d'Eratosthène Sieve

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

Image illustrant l'algo ci-dessus (cellules de couleur gris représentent le nombre premier. Étant donné que nous considérons tous les nombres comme nombres premiers Intially, l'ensemble est la grille est gris au départ.)

Image Source: WikiMedia

Answer 5

La solution la plus simple serait de revenir un membre du Collections Framework à la place d'un tableau.

Answer 6

Utilisez-Java 1.5 vous? Pourquoi ne pas retourner List<Integer> et utiliser ArrayList<Integer>? Si vous avez besoin de retourner un int[], vous pouvez le faire en convertissant Liste à int[] à la fin du traitement.

Answer 7

Comme Paul Tomblin souligne, il y a de meilleurs algorithmes.

Mais maintenant avec ce que vous avez, et en supposant un objet par résultat est trop grand:

Vous ne jamais au tableau Annexer des. Donc, utiliser un tableau relativement faible int []. Quand il est plein usage append à une liste et de créer un remplacement. A la fin le copier dans un tableau correctement dimensionné.

Vous pouvez également deviner la taille du tableau int []. Si elle est trop petite, remplacer par un int [] avec une taille d'une fraction plus grande que la taille du tableau en cours. Les frais généraux de performance de cette demeure proportionnelle à la taille. (Cela a été discuté brièvement dans un récent podcast stackoverflow.)

Answer 8

Maintenant que vous avez un tamis de base en place, notez que la boucle intérieure doit seulement continuer jusqu'à temp[i]*temp[i] > prime.

Answer 9

J'ai une implémentation très efficace:

1. nous ne gardons pas les nombres pairs, donc réduire de moitié l'utilisation de la mémoire.
2. nous utilisons BitSet, ne nécessitant qu'un seul bit par numéro.
3. nous estimons la limite supérieure pour le nombre de nombres premiers sur l'intervalle, nous pouvons donc définir la initialCapacity pour le tableau de façon appropriée.
4. nous ne réaliser aucune sorte de division dans les boucles.

Voici le code:

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

Restructurer votre code. Jetez le tableau temporaire, et au lieu d'écrire fonction juste prime teste un nombre entier. Il sera assez rapide, puisque vous êtes seulement en utilisant les types natifs. Ensuite, vous pouvez, par exemple, la boucle et construire une liste d'entiers qui sont premiers, avant de finalement convertir ce à un tableau de revenir.

Answer 11

J'ai finalement terminé le programme Il est un tamis optimisé

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

Je ne sais pas si cela la suite de votre situation, mais vous pouvez jeter un oeil à mon approche. J'utilisé le mien en utilisant Sieve de Eratosthène.

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

pour chaque commentaire Ajouté étapes qui a été illustré dans wikipedia

Answer 13

Je l'ai fait à l'aide HashMap et l'a trouvé très 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);
                    }
                }

            }
        }

    }

}

Pense que cela est 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;
            }
        }
    }