私のStreamExライブラリにはheadTail()、問題を解決する操作があります:
public static StreamEx<Integer> sieve(StreamEx<Integer> input) {
return input.headTail((head, tail) ->
sieve(tail.filter(n -> n % head != 0)).prepend(head));
}
このheadTailメソッドはBiFunction、ストリーム ターミナル操作の実行中に最大 1 回実行される を受け取ります。したがって、この実装は怠惰です。トラバーサルが開始されるまで何も計算せず、要求された数だけ素数を計算します。はBiFunction最初のストリーム要素headと残りの要素のストリームを受け取り、必要な方法でtailを変更できます。tail定義済みの入力で使用できます。
sieve(IntStreamEx.range(2, 1000).boxed()).forEach(System.out::println);
しかし、無限のストリームも機能します
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);
headTailおよび述語連結を使用した代替ソリューションもあります。
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);
再帰的なソリューションを比較するのは興味深いことです: それらが生成できる素数の数。
@John McClean ソリューション ( StreamUtils)
John McClean のソリューションは怠惰ではありません。無限のストリームを供給することはできません。だから私は試行錯誤によって最大許容上限（17793）を見つけました（その後、StackOverflowErrorが発生しました）：
public void sieveTest(){
sieve(IntStream.range(2, 17793).boxed()).forEach(System.out::println);
}
@John McClean ソリューション ( Streamable)
public void sieveTest2(){
sieve(Streamable.range(2, 39990)).forEach(System.out::println);
}
上限を超える39990と、StackOverflowError が発生します。
@frhack ソリューション ( LazySeq)
LazySeq<Integer> ints = integers(2);
LazySeq primes = sieve(ints); // sieve method from @frhack answer
primes.forEach(p -> System.out.println(p));
結果: 素数の後にスタック =53327巨大なヒープ割り当てとガベージ コレクションが 90% 以上を占めます。53323 から 53327 に進むのに数分かかったので、それ以上待つのは現実的ではないようです。
@vidiソリューション
Prime.stream().forEach(System.out::println);
結果: 素数 = の後の StackOverflowError 134417。
私の解決策 (StreamEx)
sieve(StreamEx.iterate(2, x -> x+1)).forEach(System.out::println);
結果: 素数 = の後の StackOverflowError 236167。
@frhack ソリューション ( rxjava)
Observable<Integer> primes = Observable.from(()->primesStream.iterator());
primes.forEach((x) -> System.out.println(x.toString()));
結果: 素数 = の後の StackOverflowError 367663。
@ホルガーソリューション
IntStream primes=from(2).filter(i->p.test(i)).peek(i->p=p.and(v->v%i!=0));
primes.forEach(System.out::println);
結果: 素数 = の後の StackOverflowError 368089。
私の解決策（述語連結を伴うStreamEx）
sieve(StreamEx.iterate(2, x -> x+1), i -> true).forEach(System.out::println);
結果: 素数 = の後の StackOverflowError 368287。
したがって、述語連結を含む 3 つのソリューションが優先されます。これは、新しい条件ごとにスタック フレームが 2 つ追加されるだけだからです。それらの違いはごくわずかであり、勝者を定義するものと見なすべきではないと思います. ただし、Scala コードに似ているため、最初の StreamEx ソリューションの方が気に入っています。