java - 使用流对正整数进行质因数分解

Question

我目前正在尝试将 Java 8 的 Stream API 合并到我的日常 Java 工具箱中。我正在尝试使用 Streams 来查找正整数的质因数，然后将每个因数存储在一个数组(或 ArrayList)中，并将它们的多重性存储在一个并行数组中。或者，我正在尝试创建一个 say...FactorWithMultiplicity 对象流，甚至是一个以因子为键、以多重性为值的 Map。如果因子按升序排序，并且它甚至可以处理非常大的数字(例如，我敢说，Long.MAX_VALUE)，那就太好了。

目前，我的代码看起来像这样，但是，由于我是 Streams 的初学者，我确信有一种更快或更适合的方法来完成这项任务。请使用 Streams 创建您的解决方案，但如果您知道某些非 Stream 解决方案更快，请随时向我指出该代码。

int num = getPositiveInt();
ArrayList<Integer> factors = new ArrayList<>();
ArrayList<Integer> multiplicities = new ArrayList<>();
boolean isPrime = IntStream.rangeClosed(2, num / 2)
    .reduce(num, (int temp, int factor) -> {
        int count = 0;
        while (temp % factor == 0) {
            temp /= factor;
            count++;
        }
        if (count > 0) {
            factors.add(factor);
            multiplicities.add(count);
        }
        return temp;
    }) > 1;

Answer 1

如果你特别想要一个基于流的解决方案，你可以有一个递归地分解一个数字的方法:

IntStream factors(int num) {
    return IntStream.range(2, num)
        .filter(x -> num % x == 0)
        .mapToObj(x -> IntStream.concat(IntStream.of(x), factors(num / x)))
        .findFirst()
        .orElse(IntStream.of(num));
}

然后您可以使用以下代码来制作您的两个列表:

Map<Integer, Integer> f2m = factors(2, num).boxed()
        .collect(toMap(f -> f, f -> 1, Integer::sum));  // or groupingBy with summingInt(f->1), whichever you prefer

List<Integer> factors = new ArrayList<>(f2m.keySet());
List<Integer> multiplicities = factors.stream().map(f2m::get).collect(toList());

如果您想从中获得更多性能，可以将最后找到的因子传递给 factors 方法并使用它代替 2。

如果您想对多头进行因子分解，这里有一个具有一些性能改进的版本:

static LongStream factors(long lastFactor, long num) {
    return LongStream.rangeClosed(lastFactor, (long) Math.sqrt(num))
            .filter(x -> num % x == 0)
            .mapToObj(x -> LongStream.concat(LongStream.of(x), factors(x, num / x)))
            .findFirst()
            .orElse(LongStream.of(num));
}

如果你希望结果是有序的，你可以使用

SortedMap<Long, Integer> f2m = factors(2, num).boxed()
         .collect(toMap(f -> f, f -> 1, Integer::sum, TreeMap::new));

或者，或者，保持 Map 原样并使用

List<Long> factors = f2m.keySet().stream().sorted().collect(toList());