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.

Advertisements

Author: Neil Madden

I am an independent IAM and application security consultant, with particular expertise in ForgeRock's OpenAM access management product. I have over 18 years of professional software development experience in commercial, government and academic settings. I have a PhD and 1st-class honours degree in Computer Science.

4 thoughts on “Java 8 Sieve of Eratosthenes”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s