使用单一方法获取功能 Java 流中的主要因素？

Question

此方法将为传递给该方法的任何数字接收 Long 和 return 个 LongStream 质数。

factors.java

public LongStream factors(long x){
  LongStream factorStream = LongStream.range(1, x+1).filter(n -> x%n == 0);
  return factorStream;
}

利用上面的方法先求公因数ok.

primeFactors.java

public LongStream primeFactors(long x){
  LongStream primeFactorStream = factors(x).filter(n -> factors(n).count() == 0); 
  //doesn't work as factors.java returns a LongStream, which might include non-prime factors, which will not equate to zero.
  return primeFactorStream;
}

我知道这应该很容易通过使用带有谓词的简单 isPrime() 方法来规避，但是有没有办法对 for 主要因素但只有一种方法？

Answer 1

您可以使用 BigInteger 的 isProbablePrime() 方法来检查您的因子是否为素数：

public static LongStream primeFactors(long x){
    LongStream primeFactorStream = factors(x)
            .filter(n -> new BigInteger(String.valueOf(n)).isProbablePrime(10));
    return primeFactorStream;
}

为了primeFactors(26).forEach(System.out::println);它returns2 13.

Answer 2

在没有 memoization 的情况下，使用 LongStream，您可以应用一些简单的性能改进，例如生成最多 的数字流的主要因素流x/2:

public static LongStream factors(long x){
  return LongStream.rangeClosed(2, x/2).filter(n -> x % n == 0);
}

public static LongStream primeFactors(long x){
  return LongStream.rangeClosed(2, x/2)
    .filter(n -> x % n == 0).filter(n -> factors(n).count() == 0);
}

对于非常大的 x 这很重要。但是，此解决方案为 2 个流中的每个流中的每个 n 重复 x % n == 0 的测试，这需要 memoization.

Answer 3

如果你想在不借助现有的素数测试方法的情况下在单一方法中完成，你可以像

那样做

public static LongStream primeFactors(long x) {
    return LongStream.rangeClosed(2, x)
                     .filter(n -> x % n == 0)
                     .filter(n -> LongStream.rangeClosed(2, n/2).noneMatch(i -> n%i==0));
}

你可以像这样测试方法

IntStream.concat(IntStream.rangeClosed(2, 15), IntStream.rangeClosed(90, 110))
         .forEach(number -> System.out.printf("%3d = %s%n", number,
            primeFactors(number)
                .mapToObj(d -> {
                    int p = 0;
                    for(long l = number; l%d == 0; l /= d, p++) l++;
                    return p == 1? String.valueOf(d): d + "^" + p;
                })
                .collect(Collectors.joining(" * ")))
         );
}

  2 = 2
  3 = 3
  4 = 2^2
  5 = 5
  6 = 2 * 3
  7 = 7
  8 = 2^3
  9 = 3^2
 10 = 2 * 5
 11 = 11
 12 = 2^2 * 3
 13 = 13
 14 = 2 * 7
 15 = 3 * 5
 90 = 2 * 3^2 * 5
 91 = 7 * 13
 92 = 2^2 * 23
 93 = 3 * 31
 94 = 2 * 47
 95 = 5 * 19
 96 = 2^5 * 3
 97 = 97
 98 = 2 * 7^2
 99 = 3^2 * 11
100 = 2^2 * 5^2
101 = 101
102 = 2 * 3 * 17
103 = 103
104 = 2^3 * 13
105 = 3 * 5 * 7
106 = 2 * 53
107 = 107
108 = 2^2 * 3^3
109 = 109
110 = 2 * 5 * 11

不用说，这不是最有效的方法……

使用单一方法获取功能 Java 流中的主要因素？

Getting prime factors in functional Java streams with a single method?

java

lambda

primes

functional-programming

java-stream