Ok, here you are.
A few notes first:
1) Don't concentrate on design issues. This is what I hacked out quickly (I polished it a bit, but it only helped so much). This code is ugly. The important part is mathematics, not design.
2) Some (ok, most) of the optimization were taken from the Project Euler's Problem 10 PDF:
- Skipping even number and not tracking even numbers in the sieve is obvious.
- The 6k±1 rule excludes even number and multiples of three, improving on the obvious "skip even numbers" optimization by
a factor of three a third. Well, obvious, but I missed on this. Including multiples of five would complicate things substantially with appropriately diminished returns (skipping only about one fifth of remaining numbers).
- Marking multiples of n in the sieve starting at n*n is very significant improvement, which makes processing larger numbers run much faster. Again, easy to derive, but I missed on that.
- No need to mark multiples higher than square root of largest expected number, this shortens code path slightly, but is not actually that important.
- Approximations of number of primes less than X and of upper bound for Nth prime are taken from Wikipedia (Prime Counting Theorem). I wouldn't have an ambition to derive these myself
Use
int[] primes = Primes.listOfFirstNPrimes(Primes.MAX_NUM_OF_PRIMES); to obtain the list of hundred million primes. You need to give your JVM enough memory (I've used -Xmx1024m). It runs in around 75-80 seconds on my notebook.