Return to Answer

• 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

• 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

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;
 }

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);
 }
 }

}

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;
 }