Java 8 Sieve of Eratosthenes

We had a competition at work to calculate the count and sum of all prime numbers between 1 and 1,000,000 in the shortest time. Naturally we all went for the Sieve of Eratosthenes as the best way to implement this. The fastest solution was a straightforward imperative approach, but I came up with the shortest implementation using Java 8 streams and a BitSet that comes within about 20% of the winner. It’s quite cute so I thought I’d share it. Note: it uses a stateful consumer so cannot be parallelised. I’d love to see a good stateless version if anyone can think of one.

final int limit = 1_000_000;
final BitSet sieve = new BitSet(limit+1);
final IntSummaryStatistics stats = IntStream.rangeClosed(2, limit)
                  .filter(x -> !sieve.get(x))
                  .peek(x -> {
                      if (x*x < limit)
                        for(int i = x; i <= limit; i+=x)
                           sieve.set(i);
                   })
                  .summaryStatistics();
System.out.printf("%d %d%n", stats.getCount(), stats.getSum());

Once the JIT has warmed up (run it with -server and do a few hundred loops through) it runs in about 9ms. Enjoy!

Edit (2017-01-06): fixed two bugs in the implementation.