I am working on a tutorial for my Java concurrency course. The objective is to use thread pools to compute prime numbers in parallel.

The design is based on the Sieve of Eratosthenes. It has an array of n bools, where n is the largest integer you are checking, and each element in the array represents one integer. True is prime, false is non prime, and the array is initially all true.

A thread pool is used with a fixed number of threads (we are supposed to experiment with the number of threads in the pool and observe the performance).

A thread is given a integer multiple to process. The thread then finds the first true element in the array that is not a multiple of thread's integer. The thread then creates a new thread on the thread pool which is given the found number.

After a new thread is formed, the existing thread then continues to set all multiples of it's integer in the array to false.

The main program thread starts the first thread with the integer '2', and then waits for all spawned threads to finish. It then spits out the prime numbers and the time taken to compute.

The issue I have is that the more threads there are in the thread pool, the slower it takes with 1 thread being the fastest. It should be getting faster not slower!

All the stuff on the internet about Java thread pools create n worker threads the main thread then wait for all threads to finish. The method I use is recursive as a worker can spawn more worker threads.

I would like to know what is going wrong, and if Java thread pools can be used recursively.