Naive parallel Sieve of Eratosthenes in Java

My naive version now is too slow. I think setting/accessing concurrent atomic bit is way slower compared to access/modify an array of boolean. Second, the parallel execution only happens on the beginning of the process. For bigger numbers, thread-pool is not really active.

```
public class EratosthenesSieve {

private final ExecutorService executorService;
private final int n;
private final AtomicBitSet bitSet;
private final int squareRoot;
private final Node head;
private final Node trailer;

public EratosthenesSieve(int n) {
this.n = n;
this.squareRoot = (int) Math.sqrt(n);
bitSet = new AtomicBitSet(n + 1);
executorService = Executors.newCachedThreadPool();
Node h = new Node(0, null, null);
Node t = new Node(0, null, h);
h.setNext(t);
head = h;
trailer = t;

}

public Node addLast(int i) {
Node node;
while ((node = trailer.prepend(i)) == null)
;
return node;
}

class FlagIdeal
implements Runnable {
private final int candidate;

FlagIdeal(int candidate) {
this.candidate = candidate;
}

@Override
public void run() {
int j = bitSet.firstZeroAfter(candidate);
if (j >= n) {
executorService.shutdown();
return;
}
int prime = j;
for (Node iterator = head.forward(); iterator != null; iterator = iterator.forward()) {
// with a good scheduler, it should never happen
if (prime > iterator.element) {
executorService.submit(this);
return;
}
}
// after the iteration over the list of restrictions, something may change
if (bitSet.get(prime)) {
executorService.submit(this);
return;
}
// work is over

Accumulator Strategy

One minor optimization can beat the single processing in a long run (\$n >= 100000000\$). Instead of update the directly AtomicSet for each non-prime number, you can update an intermediate variable with same size of each chunk of the AtomicSet and using this intermediate value to update the chunk once.

` // now, mark all multiples of this prime number starting from the square
int idx = 0;
long num = 0;
if (prime >> AtomicBitSet.CHUNK_BITS;
num = bit;

//bitSet.set(lastNumber); let's avoid update the bitset too often
for (lastNumber = lastNumber + prime; lastNumber = AtomicBitSet.CHUNK_SIZE){
bitSet.set(idx, num);
idx++;
num = bit;
activeRestriction.element = lastNumber;
remainingBits = remainingBits % AtomicBitSet.CHUNK_SIZE;
} else {
num = num | bit;
}
}
} else {
bitSet.set(lastNumber);

for (lastNumber = lastNumber + prime; lastNumber

StackExchange Code Review Q#131954, answer score: 7