math Prime factorization


Example

Example implementation of a prime factorization algorithm. A prime factorization algorithm will find for a given number n a list of primes, such that if you multiply those primes you get n. The below implementation will add -1 to the list of prime factors in case n < 0. Note that there exists no prime factorization of 0, therefore the method below returns an empty list.

List<Integer> primeFactors(int n) {
    List<Integer> factors = new ArrayList<>();
    if (n < 0) {
        factors.add(-1);
        n *= -1;
    }
    for (int i = 2; i <= n / i; ++i) {
        while (n % i == 0) {
            factors.add(i);
            n /= i ;
        }
    }
    if (n > 1) {
        factors.add(n);
    }
    return factors ;
}