A naive way of figuring out the number of factors of a particular number is to try every number from 1 up to the number itself.

public ArrayList getFactors(int N) {
ArrayList factors = new ArrayList();
for (int i=0; i if (N%i==0) {
factors.add(i);
}
return factors;
}

We can do much better than this by noticing that for every number i that is a factor of N; the number N/i is also a factor of N! This means that we can change out O(N) algorithm to O(sqrt(N)) which is much much faster.

public ArrayList getFactors(int N) {
ArrayList factors = new ArrayList();
int sqrt = (int) Math.sqrt(N);
for (int i=0; i if (N%i==0) {
factors.add(i);
}
if (sqrt * sqrt == N) {
factors.add(sqrt);
}
return factors;
}

Save this code somewhere, I guarantee it’ll come in handy!