Obtenir les facteurs premiers dans les flux Java fonctionnels avec une seule méthode?

Question

Cette méthode prendra un Long et renverra un LongStream de nombres premiers pour n'importe quel chiffre passé à la méthode.

factors.java

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

En utilisant la méthode ci-dessus pour trouver des facteurs communs est d'abord 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; 
} 

Je comprends cela devrait être facilement contournée par l'utilisation d'un simple, isPrime() méthode avec un prédicat, mais est-il un moyen de faire la même chose pour pour facteurs premiers mais seulement avec une seule méthode?

Answer 1

Si vous voulez le faire en une seule méthode sans l'aide d'une méthode de test pour-prime existante, vous pouvez le faire comme

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

Vous pouvez tester la méthode comme

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 

Inutile de dire que ce n'est pas l'approche la plus efficace ...

Answer 2

Vous pouvez faire usage de la méthode de isProbablePrime()BigInteger pour vérifier si vos facteurs sont premiers:

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

Pour primeFactors(26).forEach(System.out::println); il retourne 2 13.

Answer 3

Sans memoization, et en utilisant LongStream vous pouvez appliquer quelques améliorations de performance simples comme pour le flux de facteurs premiers produisant un flux de nombres jusqu'à 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); 
} 

Ce qui pour très grand x aura de l'importance. Cependant cette solution répète le test de x % n == 0 pour chaque n dans chacun des 2 flux, ce qui nécessite memoization.