How to Find Factors of a Given Number in Java

In this article, we will learn how to find distinct factors or divisors of a given number in Java.

Find Factors of a Given Number in Java

Method One: Brute Force Approach

A straightforward approach would be to traverse all the numbers starting from 1 till n and see if they divide n properly(i.e., give the remainder zero). If yes, it’s a factor else, not a factor.

Example Code:

import java.io.*;

class test {
  public static void main(String[] args) {
    int n = 24;

    for (int i = 1; i <= n; i++) {
      if (n % i == 0)
        System.out.println(i);
    }
  }
}

Output:

1
2
3
4
6
8
12
24

Method Two: Traversing Until n/2

From the first method, we can observe that rather than traversing till n, we can stop it at n/2 because any number greater than n/2 can never be the factor of the number n except the number itself.

For instance, the number n is 100, so n/2 is 50, so any number greater than 50, like 51 or 52, can never be the factor of 100.

Example Code:

import java.io.*;

class GFG {
  public static void main(String[] args) {
    int n = 24;

    for (int i = 1; i <= n / 2; i++) {
      if (n % i == 0)
        System.out.println(i);
    }

    System.out.println(n);
  }
}

In the above code, we have written an extra print statement after the loop as the number n itself is a factor.

Output:

1
2
3
4
6
8
12
24

Method Three: Traversing Until sqrt(n)

We can optimize the second method even more by making a small observation. If we see closely, we see that factors occur in pairs.

For instance, n = 100 and it’s factors are 1,2,4,5, 10, 20, 25, 50, 100. So, the different pairs possible here are (1,100), (2,50), (4,25), (5,20), (10,10).

Hence, at max, we have to check the numbers till sqrt(n); in this case, it’s 10. The last (10,10) is a special case as we know that the number is a factor.

Example Code:

import java.io.*;
class GFG {
  public static void main(String[] args) {
    int num = 24;

    for (int i = 1; i <= Math.sqrt(num); i++) {
      if (num % i == 0) {
        if (num / i == i)
          System.out.println(i);

        else {
          System.out.println(i);
          System.out.println(num / i);
        }
      }
    }
  }
}

Output:

1
24
2
12
3
8
4
6

In the above output, the factors are not sorted. We can get the sorted output using auxiliary space.

Example Code:

import java.io.*;
import java.util.*;

class GFG {
  public static void main(String[] args) {
    int num = 24;
    ArrayList<Integer> store = new ArrayList<>();
    for (int i = 1; i <= Math.sqrt(num); i++) {
      if (num % i == 0) {
        if (num / i == i)
          System.out.println(i);

        else {
          System.out.println(i);
          store.add(num / i);
        }
      }
    }

    for (int j = store.size() - 1; j >= 0; j--) System.out.println(store.get(j));
  }
}

Output:

1
2
3
4
6
8
12
24

In the above code, we used an ArrayList to store some factors and then print the contents of the ArrayList in the reverse order at the end.