package main.rice;

import java.util.ArrayList;
import java.util.List;

/**
 * This class implements a relatively simple algorithm for computing (and printing) the
 * prime factors of a number.  At initialization, a list of primes is computed. Given a
 * number, this list is used to efficiently compute the prime factors of that number.
 */
public class PrimeFactorizer {

    private final int maxNumToFactorize;
    private final int[] primes;

    public PrimeFactorizer(int maxNumToFactorize) {
        this.maxNumToFactorize = maxNumToFactorize;

        // Use Sieve of Eratosthenes to pre-compute all primes up to maxNumToFactorize
        if (maxNumToFactorize >= 2) {
            boolean[] isComposite = new boolean[maxNumToFactorize + 1];
            List<Integer> primeList = new ArrayList<>();

            for (int i = 2; i <= maxNumToFactorize; i++) {
                if (!isComposite[i]) {
                    primeList.add(i);
                    for (long j = (long) i * i; j <= maxNumToFactorize; j += i) {
                        isComposite[(int) j] = true;
                    }
                }
            }

            primes = new int[primeList.size()];
            for (int i = 0; i < primeList.size(); i++) {
                primes[i] = primeList.get(i);
            }
        } else {
            primes = new int[0];
        }
    }

    public int[] computePrimeFactorization(int numToFactorize) {
        // Return null for invalid inputs
        if (numToFactorize <= 1 || numToFactorize > maxNumToFactorize) {
            return null;
        }

        List<Integer> factors = new ArrayList<>();
        int remaining = numToFactorize;

        for (int prime : primes) {
            if ((long) prime * prime > remaining) {
                break;
            }
            while (remaining % prime == 0) {
                factors.add(prime);
                remaining /= prime;
            }
        }

        // If remaining > 1, it is a prime factor itself
        if (remaining > 1) {
            factors.add(remaining);
        }

        int[] result = new int[factors.size()];
        for (int i = 0; i < factors.size(); i++) {
            result[i] = factors.get(i);
        }
        return result;
    }
}