Was ist die eleganteste Methode zur Generierung der ersten N Primzahlen?

Eine elegante Möglichkeit, Primzahlen zu generieren

Das Ziel besteht darin, eine Funktion generatePrimes(n) zu schreiben, die die ersten n Primzahlen zurückgibt. Es gibt mehrere Möglichkeiten, diese Funktionalität zu erreichen, jede mit ihren eigenen Vor- und Nachteilen. In diesem Artikel werden die elegantesten Methoden untersucht.

Der ursprüngliche Ansatz verwendet normalerweise verschachtelte Schleifen, um Primzahlen zu überprüfen. Obwohl dieser Ansatz funktioniert, mangelt es ihm aufgrund seiner sich wiederholenden und verschachtelten Struktur an Eleganz. Ein eleganterer Ansatz ist die Verwendung des Siebs von Eratosthenes, das eine zeitliche Komplexität von O(n log log n) hat.

Das Sieb des Eratosthenes erstellt ein boolesches Array der Größe n, wobei alle Elemente zunächst auf „true“ gesetzt sind. Array-Indizes repräsentieren Zahlen von 0 bis n-1. Der Algorithmus setzt zunächst die Elemente bei Index 0 und 1 auf falsch, da es sich nicht um Primzahlen handelt. Dann werden für jeden Index i alle Vielfachen von i im Array auf „false“ gesetzt. Dieser Vorgang wird für alle Indizes bis zur Quadratwurzel von n wiederholt. Die verbleibenden wahren Elemente im Array stellen Primzahlen dar.

Hier ist eine elegante Java-Implementierung des Siebes des Eratosthenes:

<code class="language-java">public static List<Integer> generatePrimes(int n) {
    if (n <= 0) {
        return new ArrayList<>();
    }
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}</code>

Dieser Code generiert effizient und elegant die ersten n Primzahlen mithilfe des Siebs von Eratosthenes. Die Zeitkomplexität beträgt O(n log log n), der Code ist prägnant und klar und eignet sich ideal zum Generieren von Primzahlen.

Das obige ist der detaillierte Inhalt vonWas ist die eleganteste Methode zur Generierung der ersten N Primzahlen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!