Project Euler #7 using Java streams

Question

I haven't written any Java in years and I wanted to catch up a little, especially on newer features. I started looking at streams and aggregate operations and came up with the following solution to Project Euler #7 (find the 10001st prime).

package com.example;
import java.util.stream.IntStream;
import org.apache.commons.lang3.time.StopWatch;
public class Main {
 static boolean isPrime(int i) {
 int limit = (int)Math.sqrt(i)+1;
 return !IntStream.range(2, limit)
 .anyMatch(n -> i % n == 0);
 }
 public static void main(String[] args) {
 StopWatch stopWatch = new StopWatch();
 int n = 10001;
 stopWatch.start();
 int nthPrime = IntStream.iterate(2, i -> i+1)
 .filter(Main::isPrime)
 .skip(n-1)
 .findFirst().getAsInt();
 stopWatch.stop();
 System.out.printf("The %dth prime is %d\n", n, nthPrime);
 System.out.printf("Execution time: %.2fs\n", (float)stopWatch.getTime()/1000);
 }
}

Is there any obvious way to speed it up? Am I overcomplicating something? My way of getting an infinite sequence of integers, for example. Any other feedback?

• ratchet freak: one of the related questions has a stream-based implementation: codereview.stackexchange.com/a/78396/32061
• André Laszlo: Thank you! I saw that answer and it has some obvious similarities to my solution. Some differences: noneMatch instead of !anyMatch, range(2, Integer.MAX_VALUE) instead of iterate(...), collect(...) instead of skip(...).findFirst().getAsInt(). How would an experienced java developer write this? Why?

Answer 1

Is there any obvious way to speed it up? Am I overcomplicating something? My way of getting an infinite sequence of integers, for example. Any other feedback?

Well, the easiest way to speed it up is to note that there is only one even prime. So set n to 10000, start with 3 rather than 2, increment by 2 rather than 1, and you can start your isPrime range with 3 as well. It's unclear how much impact this will have, as at least those values were easy to filter.

If you have sufficient memory, you can save the generated primes and use those to do your isPrime check. You spend a lot of time checking numbers that you know won't divide the candidate. For example, you check even numbers larger than 2.

If efficiency is your goal, I'm not sure that streams are the way to go. Streams are compact to write but may be difficult to optimize. The argument in favor of streams here is that for small n, being quicker to write is more advantageous than being quick to run.

Of course, your real question may be "Given that I'm using streams, what features could I use? Not so much on this problem but on other problems where they might matter more?"

Some things that I might do in a non-stream solution that I don't know how to do with a stream (may be impossible).

1. Only generate a range of odd numbers in isPrime. Note that I've considered

    int limit = (int)(Math.sqrt(i) / 2);
    return IntStream.range(1, limit)
    .noneMatch(n -> i % (2 * n + 1) == 0);
   

   But that seems wasteful. It requires two additions and a multiplication to do what a for loop could do with a single addition. You may want to clock it to see if it's more efficient than your solution. Probably heavily dependent on the relative efficiencies of multiplication and modulus. Unless the compiler is smart enough to compile out the multiplication.

   What I really want is to either be able to set an increment to range or a limit to iterate. Either would work. Neither seems to be available.

   Note that I find noneMatch to be easier to read than !anyMatch.

2. Skip every third odd number after 3. Note that 3, 5, and 7 are all prime but 9 is not. 11 and 13 are but 15 is not. 17 and 19 are but 21 is not. What do 9, 15, and 21 have in common? They're all divisible by 3. The iterative way to do this is something like

    increment = 6 - increment;
    i += increment;
   

   Where increment starts as either 2 or 4 and will alternate between them (\6ドル-2=4\$ and \6ドル-4=2\$).

3. Use a sieve (e.g. Sieve of Eratosthenes) so as to mask out future values. Another challenge here is that a sieve doesn't fit this problem well. It finds all the primes in a range, but here you want to find a certain number of primes, not all the primes less than some maximum value.