Submitting callable tasks to a variable number of Threads in a ThreadPool
General concerns

Unrelated to multi-threading: you might want to think about fence post errors -- consider:

Assert.assertEquals(countParallel(8,10,2), countParallel(8,10,1));


Is it obvious that the code you've provided will pass this test?

Also, if a variable is only used within a given scope, it's a good idea to declare that variable within the scope....

for(int i = 0; i &lt; nrThreads; i++)
{
    Future&lt;Integer&gt; countHelper = threadPool.submit(new PrimeCounter(startFrom, startFrom + numbersPerThread));

    // gets the next chunk to be examined
    startFrom += numbersPerThread + 1;

    helperList.add(countHelper);

}


... and within a scope, to declare the variable as close as possible to its first use:

int count = 0;
for(Future&lt;Integer&gt; helper : helperList)
{
    count += helper.get();
}


I find that doing this also reveals refactorings -- for example, collapsing the outputs of all the jobs into a single number is a single idea

int sum(List&lt;Future&lt;Integer&gt;&gt; resultList) {
    int count = 0;
    for(Future&lt;Integer&gt; helper : helperList)
    {
        count += helper.get();
    }
    return count;
}


Multi-Threading

The good: you created an ExecutorService, rather than creating your own threads.  10 out of 10.

The meh: you've completely punted on cancellation.  What should be be done to the jobs that are running if an InterruptedException is thrown?  For toy problems, where you aren't supporting the ability to cancel work in progress, that's fine.  Put it on the list of things to pick up later.

You're also being, perhaps, a little bit timid about dividing up the work.  An alternative to giving each thread it's own pile of work, is to provide lots of slices of work, and let the Executor service decide which thread gets to do what.  There's nothing wrong with submitting 7 jobs to an ExecutorService with 6 threads; for that matter, it could be 70 jobs.  Or 700 jobs.

The situation you would like to avoid is one where most of your threads are idle (because there is no more work available), but one thread is taking a long time because he got all of the hard parts of the problem.

So it might be better to distribute the work more fairly -- tell each PrimeCounter that you are solving the range [1,20.000.000], but the prime counters process every nTh entry in the list (ex: one PrimeCounter checks 0,6,12..., and the next PrimeCounter checks 1,7,13..., and the last one checks 5,11,17....).


  Is there a better way of getting the values from the Future rather than saving them in a list and summing them up afterwards?


I think the answer here is: it depends.  One of the good things you've done here is ensure that values are only written by one thread; this makes lots of things easier to reason about (compared with, for instance, trying to have each PrimeCounter add values to a common accumulator).

Here, where you are using the results so close to the place that you start the jobs, it might be easier to store the intermediate results in the Runnable, wait for all the threads to finish, and then iterate the Runnables to sum up the total.  You could use ExecutorService.awaitTermination to know when the jobs have finished running, or set them up to each signal their results via a CountDownLatch, or ....

I would be more inclined to use a Future if the consumption of the result was "further away" from the calculation; like on the other side of an abstraction layer.