Факторизация - это разложение числа на произведение простых чисел.
Например: число 100 разлагается на 2 * 2 * 5 * 5.
Ниже приведена реализация на Java с алгоритмической сложностью sqrt(N).
Мы перебираем делители он 2 до квадратного корня из факторизируемого числа, и делим число на делитель, пока это возможно.
В конце остается либо 1, либо простое число, которое добавляется в результат.
List<Integer> factorization(int num) {
List<Integer> factors = new ArrayList<>();
for (int i = 2; i <= Math.sqrt(num); i++) {
while(num % i == 0) {
num /= i;
factors.add(i);
}
}
if(num != 1) {
factors.add(num);
}
return factors;
}