title: Most elegant way to generate prime numbers
body: <p>What is the most elegant way to implement this function:</p>
  
  <pre><code>ArrayList generatePrimes(int n)
  </code></pre>
  
  <p>This function generates the first <code>n</code> primes (edit: where <code>n&gt;1</code>), so <code>generatePrimes(5)</code> will return an <code>ArrayList</code> with <code>{2, 3, 5, 7, 11}</code>. (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)).</p>
  
  <p>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:</p>
  
  <pre><code>ArrayList generatePrimes(int toGenerate)
  {
      ArrayList primes = new ArrayList();
      primes.Add(2);
      primes.Add(3);
      while (primes.Count &lt; 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></pre>
  
  <p>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.</p>
  
  <p><strong>Edit</strong>: 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:</p>
  
  <ul>
  <li>A nicer version of what I originally had (Peter Smit, jmservera and Rekreativc)</li>
  <li>A very clean implementation of the sieve of Eratosthenes (starblue)</li>
  <li>Use Java's <code>BigInteger</code>s and <code>nextProbablePrime</code> for very simple code, although I can't imagine it being particularly efficient (dfa)</li>
  <li>Use LINQ to lazily generate the list of primes (Maghis)</li>
  <li>Put lots of primes in a text file and read them in when necessary (darin)</li>
  </ul>
  
  <p><strong>Edit 2</strong>: I've <a href="https://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1072205#1072205">implemented in C#</a> a couple of the methods given here, and another method not mentioned here. They all find the first <em>n</em> primes effectively (and I have a <a href="https://stackoverflow.com/questions/1042717/is-there-a-way-to-find-the-approximate-value-of-the-nth-prime/1069023#1069023">decent method</a> of finding the limit to provide to the sieves).</p>