My StreamEx library has now headTail() operation which solves the problem:
public static StreamEx<Integer> sieve(StreamEx<Integer> input) {
return input.headTail((head, tail) ->
sieve(tail.filter(n -> n % head != 0)).prepend(head));
}
The headTail method takes a BiFunction which will be executed at most once during the stream terminal operation execution. So this implementation is lazy: it does not compute anything until traversal starts and computes only as much prime numbers as requested. The BiFunction receives a first stream element head and the stream of the rest elements tail and can modify the tail in any way it wants. You may use it with predefined input:
sieve(IntStreamEx.range(2, 1000).boxed()).forEach(System.out::println);
But infinite stream work as well
sieve(StreamEx.iterate(2, x -> x+1)).takeWhile(x -> x < 1000)
.forEach(System.out::println);
// Not the primes till 1000, but 1000 first primes
sieve(StreamEx.iterate(2, x -> x+1)).limit(1000).forEach(System.out::println);
There's also alternative solution using headTail and predicate concatenation:
public static StreamEx<Integer> sieve(StreamEx<Integer> input, IntPredicate isPrime) {
return input.headTail((head, tail) -> isPrime.test(head)
? sieve(tail, isPrime.and(n -> n % head != 0)).prepend(head)
: sieve(tail, isPrime));
}
sieve(StreamEx.iterate(2, x -> x+1), i -> true).limit(1000).forEach(System.out::println);
It interesting to compare recursive solutions: how many primes they capable to generate.
@John McClean solution (StreamUtils)
John McClean solutions are not lazy: you cannot feed them with infinite stream. So I just found by trial-and-error the maximal allowed upper bound (17793) (after that StackOverflowError occurs):
public void sieveTest(){
sieve(IntStream.range(2, 17793).boxed()).forEach(System.out::println);
}
@John McClean solution (Streamable)
public void sieveTest2(){
sieve(Streamable.range(2, 39990)).forEach(System.out::println);
}
Increasing upper limit above 39990 results in StackOverflowError.
@frhack solution (LazySeq)
LazySeq<Integer> ints = integers(2);
LazySeq primes = sieve(ints); // sieve method from @frhack answer
primes.forEach(p -> System.out.println(p));
Result: stuck after prime number = 53327 with enormous heap allocation and garbage collection taking more than 90%. It took several minutes to advance from 53323 to 53327, so waiting more seems impractical.
@vidi solution
Prime.stream().forEach(System.out::println);
Result: StackOverflowError after prime number = 134417.
My solution (StreamEx)
sieve(StreamEx.iterate(2, x -> x+1)).forEach(System.out::println);
Result: StackOverflowError after prime number = 236167.
@frhack solution (rxjava)
Observable<Integer> primes = Observable.from(()->primesStream.iterator());
primes.forEach((x) -> System.out.println(x.toString()));
Result: StackOverflowError after prime number = 367663.
@Holger solution
IntStream primes=from(2).filter(i->p.test(i)).peek(i->p=p.and(v->v%i!=0));
primes.forEach(System.out::println);
Result: StackOverflowError after prime number = 368089.
My solution (StreamEx with predicate concatenation)
sieve(StreamEx.iterate(2, x -> x+1), i -> true).forEach(System.out::println);
Result: StackOverflowError after prime number = 368287.
So three solutions involving predicate concatenation win, because each new condition adds only 2 more stack frames. I think, the difference between them is marginal and should not be considered to define a winner. However I like my first StreamEx solution more as it more similar to Scala code.
iterator(). (To say nothing of the fact that your implementation isn't actually a proper prime sieve; see e.g. this paper.) – FanfaronIntStream.generate(() -> it.next()), but the iterator'shasNext()works eagerly and leads to an infinite recursion. – BrotherlyStreams at all. – Fanfaron