StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMost elegant way to generate prime numbers
text
Body
copied!<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>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 < 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>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload