// Started this review before XMas dinner. now there are many other answers. .... will post anyway....
In some ways you follow the pseudo-code, and in others you deviate. In my opinion, you follow the worst aspects of the pseudo-code, and deviate from the best.
Things that you copy, but I would change are:
- Use more meaningful variable names....
A
, i
, j
, and n
are not great names, yet you have variables a
, i
, j
, k
, and x
. Further, your a
and the pseudo-A
are different things.
Things you change, but I would copy:
- use an actual array-of-boolean for your sieve, instead of a
Map<Integer,Boolean>
Further, there are a number of other issues I have concerns with:
you create primes
as a set of the Entries in the primesMap
immediately after creating primesMap
:
Map<Integer, Boolean> primeMap = new HashMap<Integer, Boolean>();
Set<Map.Entry<Integer, Boolean>> primes = primeMap.entrySet();
For a while this had me confused.... I am flabbergasted, actually, that this works. That the primes
set is correctly populated after populating the backing Map. Now, don't get me wrong, this does appear to actually work, but I have never seen this done this way, and you have taught me something! I have confirmed in the JavaDoc that the entrySet()
is 'live', and changes as you change the backing Map. Unfortunately, I cannot recommend this practice - simply due to it's unconventionality.
- The line of code
int n = (x * ((int)Math.sqrt(x) / 10)) + x;
has me confused as well. What is this formula? Why does it work? How can you be sure that the x'th
Prime is less than this value n
? In fact, it cannot be right, the 5th prime is 11, but, in your case, n
would be 5. You should read up on this approximation of the n th prime.
- It is a
C
type construct to declare your variables at the start of a method. Don't do this. In Java you should declare your variables as close to their usage as you can. It is a 'best practice' (although there is some debate).
- In your loops you do not use convenient conditional
whiles
. The while (true) ... break; ....
is particularly concerning. You should make the conditions more explicit
So, putting everything together, I would keep things as primitives. I would also make the limit of the sieve 'dynamic', and expand it as needed... perhaps 'seeding' it with some constants.
EDIT:
... after some festive cheer, I re-visited this problem, and figured I would put together a class that incrementally calculates the primes. Call it a 'project'. This is a Sieve class:
import java.util.Arrays;
/**
* This class caches prime numbers, and is able to provide you with the prime
* numbers you want (up to close to Integer.MAX_VALUE)
*
* @author rolfl
*
*/
public class EratosthenesSieve {
// Since we play by inverting the logic of a boolean array,
// I have constants that make the logic easier to see.
private static final boolean PRIME = false;
private static final boolean NOTPRIME = true;
// Initialize to the first 5 primes.
// Note, by seeding at least one odd prime, we never have to consider even
// values in the sieve.
private int[] primes = { 2, 3, 5, 7, 11 }; // seed initial primes.
/**
* Get the n<sup>th</sup> prime
*
* @param nth
* The prime to get.
* @return the n'th prime.
*/
public int getNthPrime(final int nth) {
if (nth < 1) {
throw new IllegalArgumentException("Finding the " + nth
+ " prime number is not possible");
}
while (nth >= primes.length) {
// have not yet cached this prime.
// NOTE: Integer.MAX_VALUE happens to be prime.
// Maybe there is something we can do with that.
// The estimated n'th prime: from Wikipedia:
// http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
final int lastprime = primes[primes.length - 1];
// calculate forward to 25% of where we are, or 10% + 30 more than
// the wiki guess.
final long longapproxsize = Math.max((long) lastprime
+ ((long) lastprime >> 2),
30 + (long) (nth * Math.log(nth) * 1.1));
if (longapproxsize > Integer.MAX_VALUE) {
throw new IllegalArgumentException("The " + nth
+ " prime number is probably too large to calculate.");
}
// calculate at most 1Million primes in a loop (sieve size 1M)
// (reduces maximum memory footprint);
final int approxsize = Math.min((int) longapproxsize, lastprime + 1000000);
// only need to create a sieve for what we have not yet calculated.
// odd number after last prime.
final int startfrom = lastprime + 2;
final boolean[] sieve = new boolean[approxsize - startfrom];
for (final int prime : primes) {
// mark multiples of previously-calculated primes.
if (prime == 2) {
// can ignore 2...
continue;
}
// calculating an odd-valued start position allows us to
// optimize
// by doing double-prime steps.
int first = (prime - (startfrom % prime)) % prime;
if (((first + startfrom) & 1) == 0) {
first += prime;
}
for (int j = first; j < sieve.length; j += prime + prime) {
sieve[j] = NOTPRIME;
}
}
// OK, the sieve has been extended. But only the primes from the
// previous round have been filtered...
// our last prime was recorded in primes array.
// we need to complete the prime sequence, then extract the new
// primes.
int pcnt = primes.length;
int[] tmprime = Arrays.copyOf(primes, approxsize >> 1);
int root = (int) (Math.sqrt(approxsize) + 1);
int maxj = (int)(Math.sqrt(root) + 1);
for (int i = 0; i < sieve.length; i += 2) {
if (sieve[i] == PRIME) {
// this is a newly discovered prime.
// record it
int prime = i + startfrom;
tmprime[pcnt++] = prime;
// clear any future multiples of this prime.
// optimize by starting from square, and ignoring even
// multiples.
// need j > 0 to avoid overflow issues.
if (prime > maxj) {
continue;
}
for (int j = prime * prime; j > 0 && j < root; j += prime + prime) {
if (j - startfrom < 0 || j - startfrom >= sieve.length) {
throw new ArrayIndexOutOfBoundsException(String.format("Cannot access index %d in array with length %d", j - startfrom, sieve.length));
}
sieve[j - startfrom] = NOTPRIME;
}
}
}
// OK, we have our new primes recorded.
primes = Arrays.copyOf(tmprime, pcnt);
}
return primes[nth - 1];
}
public static void main(String[] args) {
EratosthenesSieve sieve = new EratosthenesSieve();
// From wikipedia: all primes < 1000
int[] data = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109,
113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241,
251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461,
463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547,
557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773,
787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
953, 967, 971, 977, 983, 991, 997 };
for (int i = 0; i < data.length; i++) {
int act = sieve.getNthPrime(i + 1);
if (act != data[i]) {
throw new IllegalStateException("Could not calculate "
+ (i + 1) + " prime. Expect " + data[i] + " but got "
+ act);
}
System.out.println("Prime " + (i + 1) + " is " + act);
}
for (int i = 1000000; i > 0; i += 1000000) {
int act = sieve.getNthPrime(i);
System.out.println("Prime " + i + " is " + act);
}
}
}
here is some code I think better represents what should be done.... with some optimizations for Java:
public static final int findNthPrime(final int nth) {
if (nth < 1) {
throw new IllegalArgumentException("Finding the " + nth + " prime number is not possible");
}
// we make a special case of prime number 2, so that we only need to deal with half the numbers (odd numbers only)
if (nth == 1) {
return 2;
}
// The estimated n'th prime: from Wikipedia:
// http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
// add 25% because the approximation always under-estimates.
final int approxsize = (int)(nth * Math.log(nth) * 1.25);
// because boolean arrays are initialized to false, we will reverse our logic to
// avoid re-filling the arrays, hence isnotprime instead of isprime.
boolean[] isnotprime = new boolean[approxsize];
int startfrom = 3;
while (true) {
// we may need to expand the sieve in unusual conditions.
final int root = (int)Math.sqrt(isnotprime.length) + 1;
for (int i = startfrom; i < root; i+=2) {
for (int j = i * i; j < isnotprime.length; j += i) {
isnotprime[j] = true;
}
}
// even though we have only iterated to `root`, we have actually calculated all the primes to isnotprime.length.
// let's check ahead of `root` to see if our n'th prime has been calculated.
int tmpprimecount = 1;
for (int i = 3; i < isnotprime.length; i+=2) {
if (!isnotprime[i]) {
if (++tmpprimecount == nth) {
return i;
}
}
}
throw new IllegalStateException("The Wiki approximation is supposed to be good enough to cover this.");
// we were not able to find the nth prime in the estimated space.
// expand the estimated space
// tmp.length will be odd, always.
// boolean[] tmp = Arrays.copyOf(isnotprime, 1 + isnotprime.length * 2);
// for (int i = 3; i < root; i += 2) {
// if (!tmp[i]) {
// startfrom = i;
// for (int j = isnotprime.length; j < tmp.length; j+= i) {
// tmp[j] = true;
// }
// }
// }
// isnotprime = tmp;
}