Prime sieve: improve efficiency while keeping it reasonably simple?
This is a great example of memory bound problem. If you manage to reduce the number of cache misses you can have quite a speedup.
I am providing almost identical code, only instead of boolean array I am using BitSet. Running on Server machinve, on my quite dated hardware I observe about 30% speedup without any other optimizations. Hand-optimizing the bit set functionality may speed things a little more, although I am not too much an optimist.

I am providing this example only to show how important memory (micro) management can be. I do not suggest that the original algorithm can not be optimized.

public void listPrimesThree(int maxNum) {
    long startTime = System.currentTimeMillis();

    int root = (int) Math.sqrt(maxNum);

    BitSet bs = new BitSet(maxNum+1);
    for (int m = 2; m &lt;= root; m++) {
        for (int k = m * m; k &lt;= maxNum; k += m) {
            bs.set(k);
        }
    }
    long endTime = System.currentTimeMillis();
    System.err.println((endTime - startTime) / 1000 + " s");
    for (int m = 3; m &lt;= maxNum; m += 2) {
        if (!bs.get(m)) {
            System.out.println(m);
        }
    }
}