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)
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.

Author: Neil Madden

Founder of Illuminated Security, providing application security and cryptography training courses. Previously Security Architect at ForgeRock. Experienced software engineer with a PhD in computer science. Interested in application security, applied cryptography, logic programming and intelligent agents.

4 thoughts on “Java 8 Sieve of Eratosthenes”

    1. Thanks! Fixed now to use “get” instead. Also fixed a bug in the for loop. That’s the danger of posting code snippets from memory (from a phone)…

Comments are closed.

%d bloggers like this: