Return to Revisions

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 Π(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.