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;

Correy

I feel that you are using streams are a weird way. This is because you are using it to execute a lambda to manipulate external variables, whereas normally the purpose of a stream is to map or filter the numbers in the stream itself. – Dielu

@Dielu You're right. I think it would be much better if the lambda mapped to a Stream that contains the prime factors and their multiplicities. – Correy

I think that the real solution is not to use streams for this problem at all. – Unwelcome

@StephenC Please explain. I think my solution did it perfectly well, don't you? At minimum I'm just using Streams here as a foreach loop, but reduce does even more than that. – Correy

An OO representation of a prime factor might be a small object combining factor and multiplicity. – Skidmore

@Skidmore That would be perfect! I added that as an option for a solution in the question. – Correy

@Dielu I've now created a semi-solution that does those things. You might like to take a look. – Correy

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

Elum

If you make 3 changes to this code, it will be the best! (For a Stream, otherwise this solution is basically unbeatable) First, switch everything over to Long so that much bigger numbers can be used (because this solution can eat them for breakfast). Second, change the factors method to use .rangeClosed(2, (long) Math.sqrt(num)) (HUGE speed boost). Third, add .sorted() after the .orElse (because that would be super helpful and doesn't even make a dent in speed). – Correy

I used int because that's what the question used. Skipped various performance optimizations for the same reason -- even large ints get factored very fast. I will add a long version to the answer. Adding sorted() before boxed() is pointless since toMap will not preserve the order anyway. If you want the result to be sorted, you can use toMap with TreeMap::new or else sort the output of keySet(). – Elum

Sounds good, in that case just add the performance optimizations to the long version. Also, I found that wrapping f2m with new TreeMap<>() was also an easy solution for sorting. – Correy

It's not necessary to make a Map and then wrap with TreeMap. You can make the TreeMap directly with the toMap collector. See the updated code. – Elum

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

Skidmore

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}

Ducky

Answer 4

When factoring integers, the most profitable optimisation is to try divisors until the square root of the number (inclusively, ex.: try factoring 49). Also, after checking for 2, you can check afterwards with only odd numbers.

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

Mayamayakovski

Thank you very much for that advice! It's not using Streams though, so it's not really teaching what I intended this question to teach. There's already plenty of questions for how to do this without a Stream. – Correy

Answer 5

After investigating thoroughly, I've found that this is an overwhelming improvement in speed compared to what I posted in the question. The only faster one is the one posted by @Misha after changing their factors function to use .rangeClosed(prevFactor, Math.sqrt(num)) instead. However, this other solution is the fastest solution... period... but doesn't use Streams.

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

Correy