Suggestions for improvement on Project Euler #7

Question

Here is a solution for Project Euler Problem #7.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10,001st prime number?

I've used the pseudo code from the Wikipedia page for the Sieve of Eratosthenes.

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:
     if A[i] is true:
         for j = i^2, i^2+i, i^2+2i, ..., not exceeding n :
             A[j] := false

Any suggestions would be much appreciated.

import java.util.*;

public class FindPrimesHashMap {
    public static void getPrime(int x) {
        int n = (x * ((int)Math.sqrt(x) / 10)) + x;
        int nSqrt = (int)Math.floor(Math.sqrt(n));
        int j = 0;
        int k = 0;
        Map<Integer, Boolean> primeMap = new HashMap<Integer, Boolean>();
        Set<Map.Entry<Integer, Boolean>> primes = primeMap.entrySet();
        ArrayList<Integer> primeArray = new ArrayList<Integer>();

        for (int a = 2; a < n; a++) {
            primeMap.put(a, true);
        }

        for (int i = 2; i <= nSqrt; i++) {
            if (primeMap.get(i)) {
                while (true) {
                    j = (i * i) + (k * i);
                    k++;

                    if (j > n) {
                        break;
                    }
                    primeMap.put(j, false);
                }
                j = 0;
                k = 0;
             }
        } 

        for (Map.Entry<Integer, Boolean> entry : primes) {
            if (entry.getValue()) {
                primeArray.add(entry.getKey());
            }
        }
        Collections.sort(primeArray);
        System.out.println(primeArray.get(x - 1));
}

Answer 1

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

Answer 2

You have a proliferation of cryptically named variables, making your code hard to follow.

Variables j and k are only ever used inside the while (true) loop, so they should be declared in a tighter scope. There is no need to reset j after the loop. Also, it would be easier to understand your code if you reset k = 0 before the loop rather than afterwards. The while (true) loop could be simplified to:

for (int k = 0; ; k++) {
    int j = (i * i) + (k * i);
    if (j > n) {
        break;
    }
    primeMap.put(j, false);
}

Then, why not eliminate k altogether?

for (int j = i * i; j <= n; j += i) {
    primeMap.put(j, false);
}

---

I don't see why you set n = x ⌈√x / 10⌉. It seems that you chose it as an estimate for the upper bound of your answer, though I don't understand the justification. The answer should be somewhere around p_x ≈ x ln(x).

In the end, it's not really important how you arrived at n, as long as it is large enough. An explanatory comment would have been appreciated, though.

---

Using a HashMap to implement the Sieve of Eratosthenes is not a great idea, because:

1. You want to iterate through the results consecutively
2. All of the keys were initially consecutive
3. Internally, it will be hashing each key to another number

It would be a lot simpler if you simply used an array of booleans.

Answer 3

Maybe consider a simple array of Booleans instead of primeMap, or an array of integers from indices, to get rid of that copy to another array:

1. initialization

   {0,0,2,3,4,5,6}
   

2. remove non-primes through for and while loop

   {0,0,2,3,0,5,0}
   

3. sort

   {0,0,0,0,2,3,5}
   

4. find 1^st non-zero integers index for correction or for sublist

Answer 4

Well since you didn't mention what kind of improvement you are looking for, I will share some short(LOC) and precise way to find X^th prime number.

public static BigInteger getXthPrime(final int x) {
    BigInteger prime = new BigInteger("2"); // first prime number
    int noOfPrimes = 1; // since we already considered a prime
    while(noOfPrimes != x) {
        prime = prime.nextProbablePrime();
        noOfPrimes++;
    }
    return prime;
}

NOTE : This is a very slow method and will take more time as x grow larger.