Javaストリームをエレガントに使用して、数値の素因数を求める方法はありますか？

Question

C＃から出てくる、私はいくつかのJava 8を学びたいと思っています。解決したい最初のおもちゃの問題は、Javaストリームを使用して数字n≥​​2の素因数を見つけます。

私の最初の試みは非常に厄介な感じ：私はここでの問題のカップルを持っている

// candidates stores numbers that possibly are prime factors 
ArrayList<Integer> candidates = new ArrayList<Integer>(); 
IntStream.range(2, n + 1).forEach(i -> candidates.add(i)); 

// find the prime factors from the candidates list 
ArrayList<Integer> primes = candidates.stream() 
    .reduce(new ArrayList<Integer>(), 
      // add current candidate <i> to prime list <a> if <i> divides <n> 
      // and <i> is not divided by any prime <p> stored in <a> so far 
      (a, i) -> { 
       if (n % i == 0 && a.stream().allMatch(p -> i % p != 0)) { 
        a.add(i); 
       } 
       return a; 
      }, 
      // not required in sequential streams, I think 
      (a1, a2) -> { System.out.println("ouch"); return a1; } 
    ); 

：

1. 私が使用している過負荷reduce(U, BiFunction<U, T, U>, BinaryOperator<U>)がIntStreamに定義されていませんが、 Stream<Integer>にのみしたがって

   IntStream.range(2, n + 1).reduce(…) 
   

   は機能しません。

2. reduceは、副作用に依存しているため、非常に扱いにくいと感じています。理想的には、私は骨材としてStream<Integer>を使用したいと思うし、その後、副作用なしで連結を使用し、すなわち

   /* … */.reduce(new ArrayList<Integer>().stream(), 
        (a, i) -> (n % i == 0 && a.allMatch(p -> i % p != 0)) 
           ? Stream.concat(a, Stream.of(i)) 
           : a, 
        (a1, a2) -> { System.out.println("ouch"); return a1; } 
   ) 
   

   しかし、これはconcatを使用するときに「ストリームがすでに時またはクローズ操作された」スローします。だから私は

   Stream.concat(Arrays.stream(a.toArray()), Stream.of(i)) 
   

   でaを複製しようとしたが、Stream<Integer>からStream<Object>にはいくつかの変換が起こるので、これは、コンパイルされません。

3. 私はコンバイナは必要ありませんが、私はダミーを渡す必要があります。

どのようにこれらの問題を解決できますか？ところで

---

、C＃バージョンである：

var primes = Enumerable.Range(2, n - 1) 
    .Aggregate(Enumerable.Empty<int>(), 
       (a, i) => (n % i == 0 && a.All(p => i % p != 0)) 
         ? a.Union(new int[] { i }) 
         : a 
    ) 
; 

この質問は、それは再帰的ストリームAPIを介して素因数を定義するのは非常に簡単ですWhat is the highest power of A that divides N factorial?

Answer 1

に触発されました：

public static IntStream primeFactors(int n) { 
    return IntStream.range(2, n-1) 
     .filter(i -> n % i == 0 && 
       !primeFactors(i).findAny().isPresent()); // or primeFactors(i).count() == 0 
} 

ここでは、それだけを確認しますnはiで割り切れ、iは単独では素因数がありません。この解決法は、実際に怠惰な流れを生成する。たとえば、最初の素因数のみが必要な場合は、primeFactors(1234).findFirst()を使用でき、その他は計算されません。

あなたの問題については、あなたの最初の問題は、IntStreamをStream<Integer>に変換する.boxed()を追加すると簡単に解決できます。第2の問題はより問題である。 Stream APIは、連続して並行して起動する場合と同じように動作するように開発されました。しかし、あなたのアプローチは事実上シーケンシャルなので、途中から入力番号を効率的に処理して、結果を処理済みプレフィックスと組み合わせることはできません。また、reduceを使用することは不適切です：変更可能な縮小の場合はcollectが必要です。それはcollectで正しくこれを実装するために実際に可能だとしても並列ストリームのために働くことになる（効率は疑問ですが）（でも.boxed()なし！）：

public static List<Integer> primeFactors2(int n) { 
    ObjIntConsumer<ArrayList<Integer>> accumulator = (list, i) -> { 
     if(n % i == 0 && list.stream().allMatch(p -> i % p != 0)) 
      list.add(i); 
    }; 
    return IntStream.range(2, n - 1).collect(ArrayList::new, accumulator, 
      (list1, list2) -> list2.forEach(i -> accumulator.accept(list1, i))); 
} 

私はまだ好きなのにこのソリューションは、あなたの独創的なアプローチに非常に近いですより怠惰な再帰的に定義された解。