PrimeFactorization.java by Michael Yaworski

This is a very well optimized version of my PrimeFactorization.java class. The link to my old versions can be found here.

This class uses contains two methods:

import java.util.ArrayList;
import java.math.BigInteger;

/**
 * This class is used to calculate the prime factorization of any positive integer.
 * 
 * @author Michael Yaworski of http://mikeyaworski.com
 * @version October 10, 2015
 */
public class PrimeFactorization {
    
    /**
     * Reduces the parameter n into a product of only prime numbers
     * and returns a list of those prime number factors as longs.
     * 
     * @param  n  the number to prime factorize
     * @return an ArrayList (of longs) of only prime factors of the parameter n
     */
    public static ArrayList<Long> primeFactorize(long n) {
        ArrayList<Long> primeFactors = new ArrayList<Long>();
        
        long primeFactor = 0L;

        for (long i = 2L; i <= n / i; ) { // smallest prime factor to the square root of n (largest possible factor of n)
            if (n % i == 0) { // the prime number i is a factor of n (i will never go into n if it's composite since the prime factor of that compositite number would have already been tested)
                primeFactor = i; // therefore, this is a prime factor of n
                primeFactors.add(primeFactor);
                n /= i; // divide out that prime factor from n to get the rest of the prime factors
                // don't increment i: test if this same prime factor goes into n multiple times (e.g. 18 = 2*3*3)
            } else {
                i++; // i is not a prime factor of n, so increment
            }
        }
        
        if (primeFactor < n) { // n had no more prime factors, so n is a prime factor
            primeFactors.add(n);
        } else { // n was divided down to 1, meaning that the last prime factor divided itself out. therefore, it is the last prime factor
            primeFactors.add(primeFactor);
        }
        
        return primeFactors;
    }
    
    /**
     * Reduces the parameter n into a product of only prime numbers
     * and returns a list of those prime number factors as BigIntegers.
     * 
     * @param  n  the number to prime factorize
     * @return an ArrayList (of BigIntegers) of only prime factors of the parameter n
     */
    public static ArrayList<BigInteger> primeBigFactorize(BigInteger n) {
        ArrayList<BigInteger> primeFactors = new ArrayList<BigInteger>();
        BigInteger primeFactor = BigInteger.ZERO;
    
        for (BigInteger i = new BigInteger("2"); i.compareTo(n.divide(i)) <= 0; ) {
            if (n.mod(i).longValue() == 0) {
                primeFactor = i;
                primeFactors.add(primeFactor);
                n = n.divide(i);
            } else {
                i = i.add(BigInteger.ONE);
            }
        }
        
        if (primeFactor.compareTo(n) < 0) {
            primeFactors.add(n);
        } else {
            primeFactors.add(primeFactor);
        }
        
        return primeFactors;
    }
}

With this class, you can call primeFactorization like so:

PrimeFactorization.primeFactorize(13195) // [5, 7, 13, 29]

However, this will fail when trying to prime factorize a number larger than 2 billion (231 - 1) because it is outside the range of an int literal. So, to combat against this, the use of a BigInteger can be used, or just represent it as a long by using L at the end of the number:

// add this import statement
import java.math.BigInteger;
        
PrimeFactorization.primeFactorize(new BigInteger("600851475143").longValue()) // [71, 839, 1471, 6857]
PrimeFactorization.primeFactorize(600851475143L) // [71, 839, 1471, 6857]

That will allow you to use the method on values larger than 2 billion (outside the int literal range), but still has to be less than 9 quintillion (maximum value of long) because even though we are using BigInteger which has no theoretical maximum or minimum value, we are using longValue() on the BigInteger.

The other method (primeBigFactorize(BigInteger)) uses BigInteger for all calculations, which allows you to theoretically prime factorize any number (sort of). This method is probably not needed because you probably will never have to prime factorize a number larger than 9 quintillion (even in Project Euler - Problem #3, you only have to prime factorize a number that is approximately 600 billion). However, if you did need to, that method would suffice.

And you would call it just like this (notice how there is never any conversion to long or int):

PrimeFactorization.primeBigFactorize(new BigInteger("600851475143")) // [71, 839, 1471, 6857]
DOWNLOAD

             Created: October 10, 2015
Completed in full by: Michael Yaworski