ストリームと正の整数の因数分解

Question

現在、Java 8のストリームAPIを私の日常のJavaツールボックスに組み込もうとしています。私は、ストリームを使用して正の整数の素因数を見つけようとしています。次に、各因子を並列配列に多重化して配列（またはArrayList）に格納します。代わりに、私はストリーム... FactorWithMultiplicityオブジェクト、またはMapを作成して、因子としての係数と多重度を値として作成しようとしています。要因が昇順でソートされていて、それが非常に大きな数値を扱うことができればいいです（例えば、私は、Long.MAX_VALUEと言っています）。

現在のところ、私のコードはこのように見えますが、私はStreamsの初心者ですから、このタスクを達成するためのより速く、より適切な方法があると確信しています。 Streamsを使用してソリューションを作成してください。ただし、一部の非ストリームソリューションが高速であることがわかっている場合は、そのコードにも私を指差してください。

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の代わりに使用します。

あなたはlong型を考慮したい場合は、ここではいくつかのパフォーマンスの向上とバージョンです：

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

Answer 2

整数を因数分解すると、最も収益性の高い最適化（包括的に、例：49を因数分解してみてください）数の平方根までの約数を試してみることです。また、2をチェックした後、奇数だけで後でチェックすることができます。

int num = getPositiveInt(); 
ArrayList<Integer> factors = new ArrayList<>(); 
ArrayList<Integer> multiplicities = new ArrayList<>(); 
int factor = 2; 
int f_delta = 1; // to increase by +1 only once (2 to 3) 
while ((factor*factor)<=num) { 
    int count = 0; 
    while (num % factor == 0) { 
    num /= factor; 
    count++; 
    } 
    if (count > 0) { 
    factors.add(factor); 
    multiplicities.add(count); 
    } 
    factor += f_delta; 
    f_delta = 2; 
} 

Answer 3

徹底的に調査した結果、これは私が質問に投稿したものに比べて圧倒的なスピードの向上であることがわかりました。唯一速いのは@Mishaの投稿.rangeClosed(prevFactor, Math.sqrt(num))を代わりにfactorsの機能を変更した後です。ただし、this other solutionは最速の解決策です...期間...ストリームは使用しません。

public static Map<Long, Integer> factorize(long num) { //NOW USING LONG 
    Map<Long, Integer> factors = new LinkedHashMap<>(); //NOW USING MAP 
    long lastRemainder = LongStream.rangeClosed(2, (long) Math.sqrt(num)) //NOW USING SQRT 
      .filter(x -> (x== 2||x%2>0)&&(x==3||x%3>0)&&(x==5||x%5>0)) //ADDED THIS 
      .reduce(num, (temp, factor) -> { 
       if (factor <= temp/factor) { //ADDED THIS 
        int count = 0; 
        while (temp % factor == 0) { 
         temp /= factor; 
         count++; 
        } 
        if (count > 0) 
         factors.put(factor, count); 
       } 
       return temp; 
      }); 
    if (lastRemainder != num && lastRemainder > 1) //ADDED THIS 
     factors.put(lastRemainder, 1); 
    return factors; 
} 

Answer 4

factorsOfを繰り返し呼び出す場合に便利です。

ここで考えられるのは、素数をストリームとして使用して係数をフィルタリングし、それらの多重度を決定して結果を確立するFactorTimesオブジェクトを作成することです。

public class PrimeFactors { 
    private final int limit = 1_000_000; 
    private BitSet sieve = new BitSet(limit+1); 
    public PrimeFactors(){ 
    sieve.set(2, limit); 
    long count = sieve.stream() 
    .peek(x -> { if((long)x*x < limit) 
        for(int i = x*x; i <= limit; i += x) 
         sieve.clear(i); 
       }) 
    .count(); 
    } 
    public FactorTimes[] factorsOf(int num){ 
    FactorTimes[] fts = sieve.stream() 
    .limit(num/2) 
    .filter(x -> num % x == 0) 
    .mapToObj(x -> { int n = 1; 
         int k = num/x; 
         while(k % x == 0){ k /= x; n++; } 
         return new FactorTimes(x, n); 
        }) 
    .toArray(FactorTimes[]::new); 
    return fts; 
    } 
    public static void main(String[] args){ 
    PrimeFactors pf = new PrimeFactors(); 
    for(FactorTimes ft: pf.factorsOf(4504500)){ 
     System.out.println(ft); 
    } 
    } 
} 

class FactorTimes { 
    private int factor, multiplicity; 
    public FactorTimes(int f, int m) { 
    factor = f; multiplicity = m; 
    } 
    public int getFactor() { return factor; } 
    public int getMultiplicity() { return multiplicity; } 
    public String toString(){ 
    return multiplicity > 1 ? factor + "(" + multiplicity + ")" 
          : Integer.toString(factor); } 
} 

Answer 5

いくつかの状態を追跡する必要があります。したがって、Streamsはこの作業にはあまり適していません。

Spliteratorを入力してIntStreamを作成します。今、あなたは、配列やグループ化操作を生成することができます：

public static IntStream primeFactors(int n) { 
    int characteristics = Spliterator.ORDERED | Spliterator.SORTED | Spliterator.IMMUTABLE | Spliterator.NONNULL; 
    Spliterator.OfInt spliterator = new Spliterators.AbstractIntSpliterator(Long.MAX_VALUE, characteristics) { 
    int val = n; 
    int div = 2; 

    @Override 
    public boolean tryAdvance(IntConsumer action) { 
     while (div <= val) { 
     if (val % div == 0) { 
      action.accept(div); 
      val /= div; 
      return true; 
     } 
     div += div == 2 ? 1 : 2; 
     } 
     return false; 
    } 

    @Override 
    public Comparator<? super Integer> getComparator() { 
     return null; 
    } 
    }; 
    return StreamSupport.intStream(spliterator, false); 
} 

そして、このような何かを呼び出す：あなたが希望する結果を取得する必要

int n = 40500; 
System.out.println(Arrays.toString(primeFactors(n).toArray())); 
System.out.println(primeFactors(n).boxed().collect(
    Collectors.groupingBy(Function.identity(), Collectors.summingInt(i -> 1))) 
); 

を：

[2, 2, 3, 3, 3, 3, 5, 5, 5] 
{2=2, 3=4, 5=3}