Primary factorization of a positive integer with streams

Question

I am currently trying to incorporate the Stream API Java 8 into my daily Java toolkit. I am trying to use Streams to find prime coefficients 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 a coefficient as a key and a multiplicity as a value. It would be nice if the factors were sorted in ascending order, and if it could handle very large numbers (for example, I dare say Long.MAX_VALUE ).

My code currently looks like this, but since I'm new to Streams, I'm sure there is a faster or more suitable way to accomplish this task. Use Streams to create your solution, although if you know that some non-streaming solution is faster, feel free to point to this code as well.

 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 to use a thread-based solution, you can have a method that recursively affects 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 compile 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 little more performance, you can pass the last coefficient found to the factors method and use this instead of 2 .

If you want the factor to be long, here is a version with several 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, save the Map as is and use

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

Answer 2

Another option that would be useful if you want to call factorsOf multiple times. (Somewhere I stole the main idea of ​​the sieve, fixed it.)

The idea here is to use prime numbers as a stream, filtering factors and determining their multiplicity to create FactorTimes objects that set 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 simple factors, you need to track several conditions. Therefore, Streams not suitable for this task.

What you can do is create a Spliterator to create an IntStream . Now you can generate an array or 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 the desired results:

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

Answer 4

When factoring integers, the most advantageous optimization is an attempt to divide to the square root of the number (inclusive, for example: try factoring 49). In addition, after checking at 2, you can subsequently check only with 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; } 

Answer 5

After a thorough study, I found that this is an overwhelming improvement in speed compared to what I posted in the question. The only faster one is the one @Misha sent after changing their factors function to use .rangeClosed(prevFactor, Math.sqrt(num)) . However, this is another solution - this is the fastest solution ... period ... but does not use threads.

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