Prime Factorization of a Positive Integer with Streams

Question

I am currently trying to incorporate the Stream API of Java 8 into my everyday Java toolbox. I am trying to use Streams to find the prime factors of a positive integer, and then store each of the factors in an array(or ArrayList) with their multiplicity in a parallel array. Alternatively, I'm trying to create a Stream of say... FactorWithMultiplicity objects, or even a Map with the factor as the key and the multiplicity as the value. It would be nice if the factors were sorted in ascending order, and if it could even handle very large numbers (such as, dare I say, Long.MAX_VALUE).

Currently, my code looks like this, but, as I am a beginner with Streams, I am sure there is a faster or better suited way to accomplish this task. Please use Streams to create your solution, although if you know that some non-Stream solution is faster, feel free to point me to that code also.

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

If you specifically want a streams-based solution, you can have a method that recursively factors a number:

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

Then you can use the following code to make your two lists:

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

If you want to get a bit more performance out of it, you can pass last found factor to factors method and use that instead of 2.

If you want to factor longs, here's a version with a few performance improvements:

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

If you want the result to be in sorted order, you can use

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

Or, alternatively, keep the Map as it was and use

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

Answer 2

Another variant which would be useful if you want to call factorsOf repeatedly. (I stole the basic idea of the sieve somewhere, fixed it.)

The idea here is to use the primes as the stream, filtering the factors and determine their multiplicity to create the FactorTimes objects establishing the result.

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 3

To generate prime factors you need to keep track of several states. Therefore Streams are not well suited for this task.

What you can do is to provide an own Spliterator to create an IntStream. Now you're able to generate an array or the grouping operations:

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

And call something like this:

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

You should get your desired results:

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