Какой самый элегантный способ реализовать эту функцию:

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

Эта функция генерирует первыйn простые числа (редактировать: гдеn>1), такgeneratePrimes(5) вернетArrayList с{2, 3, 5, 7, 11}, (Я делаю это в C #, но я доволен реализацией Java - или любым другим подобным языком в этом отношении (поэтому не Haskell)).

Я действительно знаю, как написать эту функцию, но когда я делал это прошлой ночью, она оказалась не так хороша, как я надеялся. Вот что я придумал:

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

Я не слишком обеспокоен скоростью, хотя я не хочу, чтобы она была явно неэффективной. Я не возражаю против того, какой метод используется (наивный или сито или что-то еще), но я хочу, чтобы он был довольно коротким и понятным, как он работает.

EditСпасибо всем, кто ответил, хотя многие не ответили на мой вопрос. Чтобы повторить, я хотел хороший чистый кусок кода, который генерирует список простых чисел. Я уже знаю, как сделать это множеством разных способов, но я склонен писать код, который не так ясен, как мог бы быть. В этой теме было предложено несколько хороших вариантов:

A nicer version of what I originally had (Peter Smit, jmservera and Rekreativc) A very clean implementation of the sieve of Eratosthenes (starblue) Use Java's BigIntegers and nextProbablePrime for very simple code, although I can't imagine it being particularly efficient (dfa) Use LINQ to lazily generate the list of primes (Maghis) Put lots of primes in a text file and read them in when necessary (darin)

Edit 2: Яреализовано в C # пара методов, приведенных здесь, и другой метод, не упомянутый здесь. Они все находят первыйn эффективно простые числа (и у меня естьдостойный метод нахождения лимита для сита).