AtomicInteger in multithreading

In the (2) case, up to 11 threads (the ten from the ExecutorService plus the main thread) are contending for access to the AtomicInteger, whereas in case (1) only the main thread accesses it. In fact, for case (1) you could use int instead of AtomicInteger.

The AtomicInteger class makes use of CAS registers. It does this by reading the value, doing the increment, and then swapping the value with the value in the register if it still has the same value that was originally read (compare and swap). If another thread has changed the value it retries by starting again : read - increment - compare-and-swap, until it is succesful.

The advantage is that this is lockless, and therefore potentially faster than using locks. But it performs poorly under heavy contention. More contention means more retries.

Edit

As @teppic points out, another problem makes case (2) slower than case (1). As the increment of numbers happens in the posted jobs, the loop condition remains true for much longer than needed. While all 10 threads of the executor are churning away to determine whether their given number is a prime, the main thread keeps posting new jobs to the executor. These new jobs don't get an opportunity to increment numbers until preceding jobs are done. So while they're on the queue numbers does not increase and the main thread can meanwhile complete one or more loops loop, posting new jobs. The end result is that many more jobs can be created and posted than the needed 1000000.

Your outer loop is: while (numbers.get() < 1000000)

This allows you to continue submitting more Runnables than intended to the ExecutorService in the main thread.

You could try changing the loop to: for(int i=0; i < 1000000; i++)

(As others have mentioned you are obviously increasing the amount of contention, but I suspect the extra worker threads are a larger factor in the slowdown you are seeing.)

As for your second question, I'm pretty sure that it is against the contract of AtomicInteger for two child threads to see the same value of getAndIncrement. So something else must be going on which I am not seeing from your code sample. Might it be that you are seeing output from two separate runs of the program?

Explain me why option (2) is more slowly?

Simply because you do it inside run(). So multiple threads will try to do it at the same time hence there will be wait s and release s. Bowmore has given a low level explanation.

In (1) it is sequential. So there will be no such a scenario.

Why threads get equal value for number despite AtomicInteger multithreading safe?

I don't see any possibility to happen this. If there's such a case it should happen from 0.