如何优雅地使用 Java 流找到数字的质因数？

Question

来自C#，想学点东西Java8.第一个想解决的玩具问题是：求一个数的质因数n≥2 使用 Java 流。

我的第一次尝试感觉非常尴尬：

// 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; }
    );

我这里有几个问题：

我使用的重载 reduce(U, BiFunction<U, T, U>, BinaryOperator<U>) 没有在 IntStream 上定义，而只在 Stream<Integer> 上定义。所以
```
IntStream.range(2, n + 1).reduce(…)
```
无效。
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 时会抛出 “流已被操作或关闭”。所以我尝试用
复制 a
```
Stream.concat(Arrays.stream(a.toArray()), Stream.of(i))
```
但这不会编译，因为发生了一些从 Stream<Integer> 到 Stream<Object> 的转换。
我不需要组合器，但我想我必须通过一个虚拟机。

如何解决这些问题？

对了，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
    )
;

这个问题的灵感来自What is the highest power of A that divides N factorial?

Answer 1

通过 Stream API 递归定义质因数非常容易：

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()，其他的不计算

至于你的问题。您的第一个问题可以很容易地解决，添加 .boxed() 将 IntStream 转换为 Stream<Integer>。第二个问题更成问题。 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)));
}

这个解决方案更接近你原来的方法，虽然我仍然喜欢更懒惰的递归定义的解决方案。

如何优雅地使用 Java 流找到数字的质因数？

How can I find the prime factors of a number using Java streams elegantly?

java

java-stream

prime-factoring