Multithreaded brute force prime generator

Your single threaded version could use a rewrite...

public Integer nextPrime() { if (++lastIndex < primes.size()) { return primes.get(lastIndex); } else { int n = primes.get(primes.size() - 1); Optional<Integer> optional = Optional.empty(); do { n += 2; int finalN = n; int sqrt = (int) Math.sqrt(n) + 1; optional = primes.stream().filter((Integer i) -> i < sqrt).filter((Integer i) -> (finalN % i) == 0).findFirst(); } while(!optional.isPresent()); primes.add(n); return primes.get(lastIndex); } } 

The changes are pretty simple - first, relocate the += 2 so that there's no need to do it once for starting the loop and once per iteration. Next, change the loop into a do-while loop, because the first iteration doesn't need a check.

After that, we can see that the break only happens at the bottom. Which means it can be part of the loop condition.

And since the only way to exit the loop was via that break, we can move the adding to primes to outside of the loop.

The result is code which is much more compact and doesn't rely on flags such as primeFound and break.

Google

Google produces a number of results if you search. E.g. Should I always use a parallel stream when possible? is a top result for "parallelStream".

Test bigger

 IntStream.range(1, 1000).forEach(i -> { long startTime1 = System.nanoTime(); long n = primeGeneratorSingleThreaded.nextPrime(); long executionTime1 = System.nanoTime() - startTime1; System.out.println(String.format("Single=> Prime: %1$d. Execution time: %2$d ns.", n, executionTime1)); long startTime2 = System.nanoTime(); n = primeGeneratorMultiThreaded.nextPrime(); long executionTime2 = System.nanoTime() - startTime2; System.out.println(String.format("Multi=> Prime: %1$d. Execution time: %2$d ns.", n, executionTime2)); System.out.println("==================================\n"); }); 

This is a horrid way to test. You never let the algorithm get up to speed. Instead you start up multiple threads and tear down multiple threads on each iteration. Do that work once and let the algorithm chug for a while.

Instead of testing a thousand sequentially and timing each prime, just get the first thousand primes via one method and then the other.

Parallelize disjoint operations

Worse, this suggests that you aren't parallelizing your search. Let's see.

 Optional<Integer> optional = list.parallelStream().filter((Integer i) -> i < sqrt).filter((Integer i) -> compositeFound.get() || (num % i) == 0).findFirst(); 

Well, that's difficult to read. Let's make it break it up into multiple lines

 Optional<Integer> optional = list.parallelStream() .filter((Integer i) -> i < sqrt) .filter((Integer i) -> compositeFound.get() || (num % i) == 0) .findFirst(); 

That's much easier to follow.

But why do this in parallel? Let's say you start by doing eight of these in parallel.

So you check if num is divisible by any of 2, 3, 5, 7, 11, 13, 17, or 19. Well, it will never be divisible by 2, because you don't allow num to be even. So that's wasted. One third of the time, it will be divisible by 3. That wastes the remaining six checks.

In any given ten numbers in sequence, three will be divisible by 3 and two will be divisible by five. At most one of those will overlap. So there's no point in checking the others four of ten times. Example:

31
32 divisible by 2
33 divisible by 3
34 divisible by 2
35 divisible by 5
36 divisible by 2
37
38 divisible by 2
39 divisible by 3
40 divisible by 2

So we find two primes but test divide by eight numbers when in fact we only needed to test two numbers (3 and 5). We skip all the even numbers, so there's five gone. There are two numbers divisible by 3 (and not 2). And one number divisible by 5 (and not 2 or 3). Why do forty divisions to find out that we only need to do twenty to get five answers?

Note that findFirst is a short-circuit operation. It ends on the first correct answer.

You might try findAny instead. Note that findFirst has to make sure that all the earlier checks finish. findAny can return the first result found, not the first of the sequence. But I don't think that's the biggest possible improvement.

Rather than parallelizing the division checks, parallelize the candidate generation. Those are disjoint, so checking 31, 33, 35, 37, 39, 41, 43, and 45 at the same time doesn't waste anything. As they fall out, switch in other numbers.

31, 33, 35, 37, 39, 41, 43, 45
31, 47, 35, 37, 49, 41, 43, 51

The second line replaces all the numbers divisible by 3 (33, 39, 45) with new numbers.

At this point, we know that all our original numbers are prime if they're still there, since everything less than 49, we only need to check 3 and 5. So we found 31, 37, 41, and 43. 35 was excluded as a multiple of 5.

Save the last number checked. So we know that 51 and below are not prime after we finish processing. Previously you would have retested 49 and 51 because you start with the last prime.

Obviously at the end, we may waste up to seven unnecessary checks. However, we only do that once for the entire thousand primes. By contrast, your original algorithm wasted checks on every number. In generating the thousandth prime, you only need to test division by twenty-two numbers. The square root of 7919 is less than 89, so the last prime to check is 83.