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:
BigInteger
s and nextProbablePrime
for very simple code, although I can't imagine it being particularly efficient (dfa)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).
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;
}