Wie effizient ist das Sieb des Eratosthenes für die Erzeugung von Primzahlen?

Eleganteste Primzahlengenerierung: Ein Sieb-Ansatz

Angesichts der Herausforderung, Primzahlen zu generieren, ist das Streben nach Eleganz im Code eine edle Aufgabe. Während es viele Methoden zum Finden von Primzahlen gibt, zeichnet sich das Sieb des Eratosthenes durch seine Einfachheit und Effizienz aus.

Das Sieb des Eratosthenes erstellt ein boolesches Array der Länge n, das die Zahlen von 1 bis n darstellt. Das Array wird zunächst für alle Elemente auf „true“ gesetzt, was anzeigt, dass jede Zahl eine potenzielle Primzahl ist. Der Algorithmus durchläuft dann das Array, beginnend bei der ersten nicht markierten Zahl, also 2. Er markiert alle Vielfachen von 2 als Nicht-Primzahlen, indem er ihre Werte im Array auf „false“ setzt. Anschließend geht es zur nächsten nicht markierten Zahl, 3, über und wiederholt den Vorgang, wobei alle Vielfachen von 3 als Nicht-Primzahl markiert werden. Dies wird bis zur letzten unmarkierten Zahl √(n) fortgesetzt.

Durch die Verwendung dieses Ansatzes reduziert das Sieb des Eratosthenes die Anzahl der zum Auffinden von Primzahlen erforderlichen Prüfungen erheblich und bietet so eine äußerst effiziente Lösung. Betrachten Sie die folgende Java-Implementierung des Sieve:

<code class="java">public static BitSet computePrimes(int limit) {
    BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j < limit; j += i) {
                primes.clear(j);
            }
        }
    }
    return primes;
}</code>

Dieser Code erstellt ein BitSet zur Darstellung der Zahlen von 1 bis n und setzt alle Elemente zunächst auf true. Anschließend wird das Array durchlaufen und alle Vielfachen jeder Primzahl (beginnend mit 2) als Nicht-Primzahlen markiert. Das Ergebnis ist ein BitSet, bei dem die einzigen auf true gesetzten Elemente die Primzahlen darstellen.

Das obige ist der detaillierte Inhalt vonWie effizient ist das Sieb des Eratosthenes für die Erzeugung von Primzahlen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!