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:

• `long` type to do all of the calculations, which limits the maximum value to prime factorize to a little over 9 quintillion (263 - 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
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
} else { // n was divided down to 1, meaning that the last prime factor divided itself out. therefore, it is the last prime factor
}

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;
n = n.divide(i);
} else {
}
}

if (primeFactor.compareTo(n) < 0) {
} else {
}

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]
```