Jaki jest najbardziej elegancki sposób wdrożenia tej funkcji:

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

Ta funkcja generuje pierwsząn liczby pierwsze (edycja: gdzien>1), więcgeneratePrimes(5) zwróciArrayList z{2, 3, 5, 7, 11}. (Robię to w języku C #, ale cieszę się z implementacji Javy - lub jakiegokolwiek innego podobnego języka (nie Haskell)).

Wiem, jak napisać tę funkcję, ale kiedy to zrobiłem zeszłej nocy, nie skończyło się tak miło, jak miałem nadzieję. Oto, co wymyśliłem:

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

Nie przejmuję się zbytnio szybkością, chociaż nie chcę, żeby była ona oczywiście nieefektywna. Nie przeszkadza mi, która metoda jest używana (naiwna, sita lub cokolwiek innego), ale chcę, aby była dość krótka i oczywista, jak to działa.

Edytować: Dziękuję wszystkim, którzy odpowiedzieli, chociaż wielu nie odpowiedziało na moje aktualne pytanie. Powtarzam, chciałem ładnego, czystego fragmentu kodu, który wygenerowałby listę liczb pierwszych. Wiem już, jak to zrobić na wiele różnych sposobów, ale jestem skłonny pisać kod, który nie jest tak jasny, jak mógłby być. W tym wątku zaproponowano kilka dobrych opcji:

Miła wersja tego, co pierwotnie miałem (Peter Smit, jmservera i Rekreativc)Bardzo czyste wykonanie sita Eratostenesa (gwiazda niebieska)Użyj JavaBigIntegers inextProbablePrime dla bardzo prostego kodu, chociaż nie wyobrażam sobie, żeby był szczególnie wydajny (dfa)Użyj LINQ, aby leniwie wygenerować listę liczb pierwszych (Maghis)Umieść wiele liczb pierwszych w pliku tekstowym i przeczytaj je w razie potrzeby (darin)

Edytuj 2: Mamzaimplementowane w C # kilka podanych tutaj metod i inna metoda nie wymieniona tutaj. Wszyscy znajdują pierwszen liczby pierwsze skutecznie (i mamprzyzwoita metoda znalezienia limitu na sita).