Qual é a maneira mais elegante de implementar essa função:

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

Esta função gera o primeiron primos (editar: onden>1), assimgeneratePrimes(5) retornará umArrayList com{2, 3, 5, 7, 11}. (Eu estou fazendo isso em C #, mas estou feliz com uma implementação Java - ou qualquer outra linguagem semelhante para esse assunto (por isso não Haskell)).

Eu sei como escrever essa função, mas quando fiz isso na noite passada, não foi tão legal quanto eu esperava. Aqui está o que eu criei:

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

Não estou muito preocupado com a velocidade, embora não queira que ela seja obviamente ineficiente. Eu não me importo com qual método é usado (ingênuo ou peneira ou qualquer outra coisa), mas eu quero que seja razoavelmente curto e óbvio como isso funciona.

Editar: Obrigado a todos que responderam, embora muitos não tenham respondido à minha pergunta. Para reiterar, eu queria um bom código limpo que gerasse uma lista de números primos. Eu já sei como fazer várias maneiras diferentes, mas estou propenso a escrever código que não seja tão claro quanto poderia ser. Neste tópico, algumas boas opções foram propostas:

Uma versão melhor do que eu tinha originalmente (Peter Smit, jmservera e Rekreativc)Uma implementação muito limpa da peneira de Eratóstenes (estrela azul)Use Java'sBigIntegerareianextProbablePrime para código muito simples, embora eu não possa imaginar que seja particularmente eficiente (dfa)Use o LINQ para gerar preguiçosamente a lista de primos (Maghis)Coloque lotes de primos em um arquivo de texto e leia-os quando necessário (darin)

Editar 2: Eu tenhoimplementado em c # alguns dos métodos dados aqui e outro método não mencionado aqui. Todos eles encontram o primeiron primos efetivamente (e eu tenho ummétodo decente de encontrar o limite para fornecer às peneiras).