# Why is this solution so slow and how to make is faster?

• The idea is to recursively choose the least possible factor and add it into the list, while at the same time update `n`. Currently, it is over 300ms! I tried to mimic other solutions by changing `i*i<=n` but it does not work.

Can someone take a look?

``````public List<List<Integer>> getFactors(int n) {
List<List<Integer>> list =  getFactors(n, n, 2);
if(list.isEmpty() || list.get(0).isEmpty()) return new LinkedList<List<Integer>>();
return list;
}

private List<List<Integer>> getFactors(int n, int rem, int min) {
if(rem<=1) {
return list;
}
for(int i=min; i<=rem && i<=n/min; i++) {
if(rem%i==0) {
List<List<Integer>> prev = getFactors(n, rem/i, i);
for(List<Integer> inner : prev) {
}
}
}
return list;
}
``````

• This post is deleted!

• Q: Why is it so slow?
A: upper bound of for loop is sqrt(n), not n/min

Q: when you use sqrt(n) why it doesn't work?
A: in for loop you are asking the function to return N-tuples that multiplies to be n, but most people miss the 2-tuple made up by [i,i/n]

Below is the the code using your API, I pruned the parameters a bit also, it's 4ms, when you get rid of Arrays.asList it's 2-3 ms.

``````public List<List<Integer>> getFactors(int n) {
return getFactors(n, 2);
}

private List<List<Integer>> getFactors(int n, int min) {

int end = (int) Math.sqrt(n);
for (int i = min; i <= end; i++) {
if (n % i != 0) continue;

List<List<Integer>> prev = getFactors(n / i, i);
}

return list;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.