Primzahlen mit dem Sieb des Eratosthenes zu finden (Ursprünglich: Gibt es einen besseren Weg, um dieses Feld zu bereiten?)

Question

Hinweis: Version 2, unten, verwendet das Sieb des Eratosthenes. Es gibt mehrere Antworten, die mit dazu beigetragen, was ich ursprünglich gebeten. Ich habe das Sieb des Eratosthenes Methode gewählt, implementiert es, und änderte die Frage Titel und Tags angemessen. Vielen Dank an alle, die geholfen haben!

Einführung

Ich schrieb diese hübsche kleine Methode, die ein Array von int erzeugt die Primzahlen, die weniger als die angegebenen Obergrenze. Es funktioniert sehr gut, aber ich habe ein Problem.

Die Methode

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

Meine Sorge

Meine Sorge ist, dass ich ein Array bin schaffen, die viel zu groß für die endgültige Anzahl der Elemente der Methode zurückzukehren. Das Problem ist, dass ich nicht eine gute Art und Weise weiß es richtig, die Anzahl der Primzahlen zu erraten, weniger als eine bestimmten Anzahl.

Fokus

Dies ist, wie das Programm der Arrays verwendet. Dies ist, was ich auf verbessern will.

1. Ich erstelle eine temporäre Array, das ist groß genug, um jede Zahl zu halten kleiner als der Grenzwert.
2. I erzeugen, um die Primzahlen, während halten zu zählen, wie viele ich habe erzeugt wird.
3. Ich mache ein neues Array, das ist das Recht Dimension nur die prim zu halten Zahlen.
4. Ich kopiere jede Primzahl aus der großes Array an das Array der richtige Dimension.
5. Ich kehre das Array der korrekten Dimension, die nur das Prime hält Ich Zahlen erzeugt.

Fragen

1. Kann ich den ganzen Brocken (auf einmal) Kopie temp[], die ungleich Null hat Elemente primes[] ohne durch iterieren Beide Arrays und kopieren die Elemente eins nach dem anderen?
2. Gibt es irgendwelche Datenstrukturen, die verhalten sich wie ein Array von Primitiven das kann wachsen als Elemente hinzugefügt werden, anstatt eine Dimension erfordern bei der Instanziierung? Was ist der Leistungseinbuße im Vergleich zu unter Verwendung einer Anordnung von Primitiven?

---

Version 2 (dank 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);
}

---

Version 3 (dank Paul Tomblin ), die die Sieve von 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

Ihre Methode Primzahlen zu finden, durch jedes einzelne Element des Arrays mit jedem möglichen Faktor zu vergleichen ist scheußlich ineffizient. Sie können es immens verbessern, indem sie auf einmal eine Sieb des Eratosthenes über die gesamte Gruppe zu tun. Neben weit weniger Vergleiche zu tun, es nutzt auch zusätzlich anstatt Division. Division ist viel langsamer.

Answer 2

ArrayList<> Sieb des Eratosthenes

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

Formel für die obere Grenze der Anzahl der Primzahlen kleiner oder gleich max (siehe wolfram.com ):

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

Answer 3

ein ArrayList<Integer> erstellen und dann zu einem int[] am Ende umwandeln.

Es gibt verschiedene 3rd-Party-IntList (etc) Klassen um, aber es sei denn, du bist wirklich Sorgen um den Hit ein paar Zahlen von Boxen, würde ich nicht darum kümmern.

obwohl

Sie könnten Arrays.copyOf verwenden Sie das neue Array zu erstellen. Sie können auch durch eine Verdoppelung der Größe jedes Mal, wenn Sie brauchen, um die Größe mögen, und dann am Ende trimmen. Das wäre im Grunde das ArrayList Verhalten wird nachgeahmt wird.

Answer 4

Algo mit Sieb des Eratosthenes

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

Bild, welches den oben algo (Gray Farbzellen darstellen Primzahl. Da wir alle Zahlen als Primzahlen intially betrachten, das Ganze ist Gitter ist grau zunächst.)

Bildquelle: WikiMedia

Answer 5

Die einfachste Lösung wäre, ein Mitglied der Collections Framework zurückzukehren anstelle eines Arrays.

Answer 6

Sind Sie mit Java 1.5? Warum nicht List<Integer> zurückkehren und ArrayList<Integer> benutzen? Wenn Sie benötigen einen int[] zurückkehren, können Sie es tun, indem Liste Umwandlung am Ende der Verarbeitung int[].

Answer 7

Wie Paul Tomblin weist darauf hin, es gibt bessere Algorithmen.

Aber halten mit dem, was du hast, und ein Objekt pro Ergebnis unter der Annahme ist zu groß:

Sie sind Anfügen sich immer nur auf dem Array. So verwenden Sie ein relativ kleines int [] array. Verwendung hängen Sie sich auf eine Liste, wenn es voll ist und einen Ersatz schaffen. Am Ende kopieren Sie sie in einem richtig dimensioniert Array.

Alternativ denke, die Größe des int [] array. Wenn es zu klein ist, ersetzen durch einen int [] mit einer Größe einen Bruchteil größer als die aktuelle Feldgröße. Die Performance-Overhead dies wird auf die Größe proportional bleiben. (Dies wurde kürzlich in einem Podcast Stackoverflow kurz diskutiert.)

Answer 8

Nun, da Sie eine grundlegende Sieb anstelle haben, beachten Sie, dass die innere Schleife nur bis temp[i]*temp[i] > prime fortsetzen muss.

Answer 9

Ich habe eine wirklich effiziente Implementierung:

1. wir nicht halten die geraden Zahlen, also die Speichernutzung zu halbieren.
2. verwenden wir BitSet und erfordert nur ein Bit pro Nummer.
3. schätzen wir die Obergrenze für die Anzahl der Primzahlen auf dem Intervall, so können wir die initialCapacity für das Array entsprechend gesetzt.
4. wir führen Sie keine Art von Teilung in den Schleifen.

Hier ist der 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

Umstrukturieren Code. Werfen das temporäre Array aus, und statt dessen Funktion schreiben, die nur eine ganzzahlige Primzahl Tests. Es wird recht schnell sein, da Sie nur native Typen verwenden. Dann können Sie zum Beispiel Schleife und eine Liste von ganzen Zahlen bauen, die Primzahlen sind, bevor sie schließlich, dass in ein Array konvertieren zurückzukehren.

Answer 11

Ich beendete schließlich das Programm Es ist ein optimiertes Sieb

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

Nicht sicher, ob dies Ihre Situation Hotel, aber Sie können einen Blick auf meinem Ansatz. Früher habe ich meine mit Sieb des Eratosthenes .

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

hinzugefügt Kommentar für jeden Schritt, die in wikipedia dargestellt wurden

Answer 13

Ich habe mit HashMap gemacht und fand es sehr einfach

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

            }
        }

    }

}

Ich glaube, das wirksam ist,

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