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:
long
type to do all of the calculations, which limits the maximum value to prime factorize to a little over 9 quintillion (2^{63} - 1):
BigInteger
class to do all of the calculations, which has no theoretical limit for the value to prime factorize.
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 (2^{31} - 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