Suggestions for improvement on Project Euler #7

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 primeMap = new HashMap();
        Set> primes = primeMap.entrySet();
        ArrayList primeArray = new ArrayList();

        for (int a = 2; a  n) {
                        break;
                    }
                    primeMap.put(j, false);
                }
                j = 0;
                k = 0;
             }
        } 

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

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 px ≈ 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:

• You want to iterate through the results consecutively

• All of the keys were initially consecutive

• Internally, it will be hashing each key to another number

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

StackExchange Code Review Q#38084, answer score: 6