¿Cuál es la forma más elegante de implementar esta función:

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

Esta función genera la primeran primos (editar: donden>1), asi quegeneratePrimes(5) devolverá unArrayList con{2, 3, 5, 7, 11}. (Estoy haciendo esto en C #, pero estoy contento con una implementación de Java, o cualquier otro lenguaje similar para esa materia (así que no con Haskell)).

Sé cómo escribir esta función, pero cuando la hice anoche no terminó tan bien como esperaba. Aquí está lo que se me ocurrió:

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

No me preocupa demasiado la velocidad, aunque no quiero que sea obviamente ineficiente. No me importa qué método se use (ingenuo, tamiz o cualquier otra cosa), pero quiero que sea bastante corto y obvio cómo funciona.

Editar: Gracias a todos los que respondieron, aunque muchos no respondieron mi pregunta real. Para reiterar, quería un buen código limpio que generara una lista de números primos. Ya sé cómo hacerlo de diferentes maneras, pero soy propenso a escribir código que no sea tan claro como podría ser. En este hilo se han propuesto algunas buenas opciones:

Una mejor versión de lo que originalmente tenía (Peter Smit, jmservera y Rekreativc)Una implementación muy limpia del tamiz de Eratóstenes (starblue)Usar javaBigIntegers ynextProbablePrime para código muy simple, aunque no puedo imaginar que sea particularmente eficiente (dfa)Usa LINQ para generar perezosamente la lista de números primos (Maghis)Coloque muchos números primos en un archivo de texto y léalos cuando sea necesario (darin)

Editar 2: Heimplementado en C # Un par de los métodos dados aquí, y otro método no mencionado aquí. Todos encuentran el primero.n prepara de manera efectiva (y tengo unmétodo decente de encontrar el límite a proporcionar a los tamices).