Collecting data with streams - Java 8 in Action: Lambdas, Streams, and Functional-Style Programming - page 185

Listing 6.6. Partitioning the first n natural numbers into primes and
nonprimes
public Map<Boolean, List<Integer>> partitionPrimes(int n) {
return IntStream.rangeClosed(2, n).boxed()
.collect(partitioningBy(candidate -> isPrime(candidate));
}
There you achieved an improvement over the original isPrime method by limiting the number of
divisors to be tested against the candidate prime to those not bigger than the candidate's square
root:
public boolean isPrime(int candidate) {
int candidateRoot = (int) Math.sqrt((double) candidate);
return IntStream.rangeClosed(2, candidateRoot)
.noneMatch(i -> candidate % i == 0);
}
Is there a way to obtain even better performances? The answer is yes, but for this you'll have to
develop a custom collector.
6.6.1. Divide only by prime numbers
One possible optimization is to test only if the candidate number is divisible by prime numbers.
It's pointless to test it against a divisor that's not itself prime! So you can limit the test to only
the prime numbers found before the current candidate. The problem with the predefined
collectors you've used so far, and the reason you have to develop a custom one, is that during the
collecting process you don't have access to the partial result. This means that when testing
whether a given candidate number is prime or not, you don't have access to the list of the other
prime numbers found so far.
Suppose you had this list; you could pass it to the isPrime method and rewrite it as follows:
public static boolean isPrime(List<Integer> primes, int candidate) {
return primes.stream().noneMatch(i -> candidate % i == 0);
}
Also, you should implement the same optimization you used before and test only with primes
smaller than the square root of the candidate number. So you need a way to stop testing whether