Factors

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.

F(x) vs F(sqrt(X))
O(N) algorithm vs O(sqrt(N)) algorithm
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!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.