Most elegant way to generate prime numbers [closed]

Question

What is the most elegant way to implement this function:

ArrayList generatePrimes(int n) 

This function generates the first n primes (edit: where n>1), so generatePrimes(5) will return an ArrayList with {2, 3, 5, 7, 11}. (I'm doing this in C#, but I'm happy with a Java implementation - or any other similar language for that matter (so not Haskell)).

I do know how to write this function, but when I did it last night it didn't end up as nice as I was hoping. Here is what I came up with:

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

I'm not too concerned about speed, although I don't want it to be obviously inefficient. I don't mind which method is used (naive or sieve or anything else), but I do want it to be fairly short and obvious how it works.

Edit: Thanks to all who have responded, although many didn't answer my actual question. To reiterate, I wanted a nice clean piece of code that generated a list of prime numbers. I already know how to do it a bunch of different ways, but I'm prone to writing code that isn't as clear as it could be. In this thread a few good options have been proposed:

• 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: I've implemented in C# a couple of the methods given here, and another method not mentioned here. They all find the first n primes effectively (and I have a decent method of finding the limit to provide to the sieves).

Answer 1

Use the estimate

pi(n) = n / log(n) 

for the number of primes up to n to find a limit, and then use a sieve. The estimate underestimates the number of primes up to n somewhat, so the sieve will be slightly larger than necessary, which is ok.

This is my standard Java sieve, computes the first million primes in about a second on a normal laptop:

public static BitSet computePrimes(int limit) {     final BitSet primes = new BitSet();     primes.set(0, false);     primes.set(1, false);     primes.set(2, limit, true);     for (int i = 0; i * i < limit; i++)     {         if (primes.get(i))         {             for (int j = i * i; j < limit; j += i)             {                 primes.clear(j);             }         }     }     return primes; }