Wie findet man effizient Primzahlen innerhalb eines bestimmten Bereichs?

Primzahlen in einem gegebenen Bereich finden

In der Mathematik sind Primzahlen ganze Zahlen größer als 1, die durch keine andere Zahl außer 1 und sich selbst teilbar sind. Das Finden von Primzahlen innerhalb eines bestimmten Bereichs kann eine häufige Programmieraufgabe sein. Hier ist eine detaillierte Erklärung, wie man dieses Problem in JavaScript angeht:

Brute-Force-Ansatz

Das bereitgestellte Code-Snippet versucht, Primzahlen zwischen 0 und 100 mithilfe eines Brute-Force-Ansatzes zu finden. Es prüft, ob die Zahl durch eine beliebige Zahl von 2 bis 12 teilbar ist und gibt die Zahl zurück, wenn keine Teiler gefunden werden. Dieser Ansatz hat jedoch mehrere Nachteile:

• Er ist ineffizient, insbesondere für größere Bereiche.
• Es ist schwierig, ihn zu erweitern, um Primzahlen für größere Bereiche zu finden.

Sieb des Eratosthenes

Ein effizienterer Algorithmus zum Finden von Primzahlen heißt Sieb des Eratosthenes. So funktioniert es:

1. Erstellen Sie ein Array namens Sieve mit einer Länge von maximal 1.
2. Initialisieren Sie alle Elemente im Array auf „false“ (angenommen, „false“ bedeutet, dass die Zahl eine Primzahl ist).
3. Iterieren Sie das Sieb-Array von 2 bis zur Quadratwurzel von max.
4. Markieren Sie für jede Primzahl i alle ihre Vielfachen als Nicht-Primzahl, indem Sie sieve[i j] festlegen. zu wahr für alle j von i j bis max.
5. Nach der Iteration sind die nicht markierten Zahlen im Sieb-Array Primzahlen.

In JavaScript ist der Code für Das Sieb des Eratosthenes sieht folgendermaßen aus:

<code class="js">function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}</code>

Dieser Ansatz hat eine zeitliche Komplexität von O(n log log n), was viel effizienter ist als der Brute-Force-Ansatz.

Das obige ist der detaillierte Inhalt vonWie findet man effizient Primzahlen innerhalb eines bestimmten Bereichs?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!