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!