PrimeFactorization.java by Michael Yaworski

This class contains two public methods:

long type to do all of the calculations, which limits the maximum value to prime factorize to a little over 9 quintillion (2⁶³ - 1):
BigInteger class to do all of the calculations, which has no theoretical limit for the value to prime factorize.

import java.util.HashMap;
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 April 13, 2020
 */
public class PrimeFactorization {
  /**
   * Helper method to add a prime factor to a mapping of factors => multiplicities.
   */
  private static void setPrimeFactor(HashMap<Long, Long> primeFactors, Long primeFactor) {
    Long multiplicity = primeFactors.containsKey(primeFactor) ? primeFactors.get(primeFactor) : 0;
    primeFactors.put(primeFactor, multiplicity + 1);
  }

  /**
   * Helper method to add a prime factor to a mapping of factors => multiplicities.
   */
  private static void setBigPrimeFactor(HashMap<BigInteger, BigInteger> primeFactors, BigInteger primeFactor) {
    BigInteger multiplicity = primeFactors.containsKey(primeFactor) ? primeFactors.get(primeFactor) : BigInteger.ZERO;
    primeFactors.put(primeFactor, multiplicity.add(BigInteger.ONE));
  }

  /**
   * Reduces the integer n into a product of prime factors
   * and returns a mapping from the prime factor to its multiplicity.
   * 
   * @param n The BigInteger number to prime factorize.
   * @return A HashMap where each key is a prime factor and each value is its multiplicty.
   */
  public static HashMap<Long, Long> primeFactorize(long n) {
    HashMap<Long, Long> primeFactors = new HashMap<>();
    Long multiplicity;
    long primeFactor = 0L;
    long i = 2L;

    while (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
        setPrimeFactor(primeFactors, 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
      }
    }

    // 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
    if (primeFactor < n) primeFactor = n;
    setPrimeFactor(primeFactors, primeFactor);
    
    return primeFactors;
  }
  
  /**
   * Reduces the integer n into a product of prime factors
   * and returns a mapping from the prime factor to its multiplicity.
   * 
   * @param n The BigInteger number to prime factorize
   * @return A HashMap where each key is a prime factor and each value is its multiplicty.
   */
  public static HashMap<BigInteger, BigInteger> primeBigFactorize(BigInteger n) {
    HashMap<BigInteger, BigInteger> primeFactors = new HashMap<>();
    BigInteger primeFactor = BigInteger.ZERO;
    BigInteger i = new BigInteger("2");

    while (i.compareTo(n.divide(i)) <= 0) {
      if (n.mod(i).longValue() == 0) {
        primeFactor = i;
        setBigPrimeFactor(primeFactors, primeFactor);
        n = n.divide(i);
      } else {
        i = i.add(BigInteger.ONE);
      }
    }
    
    if (primeFactor.compareTo(n) < 0) primeFactor = n;
    setBigPrimeFactor(primeFactors, primeFactor);
    
    return primeFactors;
  }
}

With this class, you can call primeFactorization like so:

PrimeFactorization.primeFactorize(13195) // {5=1, 7=1, 13=1, 29=1}

However, this will fail when trying to prime factorize a number larger than 2 billion (2³¹ - 1) because it is outside the range of an int literal. To solve this problem, a long can be used by including an L at the end of the number:

PrimeFactorization.primeFactorize(600851475143L) // {71=1, 839=1, 1471=1, 6857=1}

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=1, 839=1, 1471=1, 6857=1}

Download

Created: October 10, 2015
Last updated: April 13, 2020
Completed in full by: Michael Yaworski