Was ist die eleganteste Art, diese Funktion zu implementieren:

<code>ArrayList generatePrimes(int n)
</code>

Diese Funktion generiert die ersten Primzahlen (edit: wheren>1), sogeneratePrimes(5) wird ein zurückgebenArrayList mit{2, 3, 5, 7, 11}. (Ich mache das in C #, bin aber zufrieden mit einer Java-Implementierung - oder einer ähnlichen Sprache (also nicht Haskell)).

Ich weiß, wie man diese Funktion schreibt, aber als ich sie letzte Nacht gemacht habe, war sie nicht so schön, wie ich es mir erhofft hatte. Folgendes habe ich mir ausgedacht:

<code>ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime += 2;
            }
        }
        primes.Add(nextPrime);
    }
    return primes;
}
</code>

Ich mache mir keine allzu großen Sorgen um die Geschwindigkeit, obwohl ich nicht möchte, dass sie offensichtlich ineffizient ist. Ich habe nichts dagegen, welche Methode verwendet wird (naiv oder Sieb oder irgendetwas anderes), aber ich möchte, dass es ziemlich kurz und offensichtlich ist, wie es funktioniert.

Bearbeiten: Danke an alle, die geantwortet haben, obwohl viele meine eigentliche Frage nicht beantwortet haben. Um es noch einmal zu wiederholen, ich wollte ein schönes, sauberes Stück Code, das eine Liste von Primzahlen generiert. Ich weiß bereits, wie man es auf verschiedene Arten macht, aber ich neige dazu, Code zu schreiben, der nicht so klar ist, wie er sein könnte. In diesem Thread wurden einige gute Optionen vorgeschlagen:

Eine schönere Version von dem, was ich ursprünglich hatte (Peter Smit, jmservera und Rekreativc)Eine sehr saubere Umsetzung des Siebs von Eratosthenes (sternblau)Verwenden Sie JavaBigIntegers undnextProbablePrime für sehr einfachen Code, obwohl ich mir nicht vorstellen kann, dass er besonders effizient ist (dfa)Verwenden Sie LINQ, um die Liste der Primzahlen (Maghis) träge zu generieren.Setze viele Primzahlen in eine Textdatei und lies sie bei Bedarf ein (darin)

Bearbeiten 2: Ich habeimplementiert in C # Einige der hier angegebenen Methoden und eine andere hier nicht erwähnte Methode. Sie alle finden die erstenn Primzahlen effektiv (und ich habe eineanständige Methode die Grenze zu finden, um die Siebe zur Verfügung zu stellen).