Java Examples

Java Program - Find all factors of a Number



Objective: Write a Java program to find all distinct factors (divisors) of a given natural number. The divisors of few numbers are given below:

 Number: 10
 Divisors: 1 2 5 10

 Number: 15
 Divisors: 1 3 5 15

 Number: 100
 Divisors: 1 2 4 5 10 20 25 50 100 

Method 1: Using iteration

One of the basic approach is to iterate from 1 to n and in each iteration check whether the number divides n. If it divides then print it.

public class MyClass {
  //method to print all divisors of a number
  static void printDivisors(int n) {
    System.out.print("Divisors of " + n + " are: ");
    for(int i = 1; i <= n; i++) {
      if(n%i == 0)
        System.out.print(i + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    printDivisors(10);
    printDivisors(50);
    printDivisors(100);
  }
}

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100 

Method 2: Optimized Code

Instead of checking the divisibility of the given number from 1 to n, it is checked till square root of n. For a factor larger than square root of n, there must the a smaller factor which is already checked in the range of 1 to square root of n.

import java.lang.Math;

public class MyClass {
  //method to print all divisors of a number
  static void printDivisors(int n) {
    System.out.print("Divisors of " + n + " are: ");
    //loop from 1 to Math.sqrt(n)
    for(int i = 1; i <= Math.sqrt(n); i++) {
      if(n%i == 0) {
        if(n/i == i)
          System.out.print(i + " ");
        else
          System.out.print(i + " " + n/i + " ");
      }
    }
    System.out.println();
  }

  public static void main(String[] args) {
    printDivisors(10);
    printDivisors(50);
    printDivisors(100);
  }
}

The above code will give the following output:

Divisors of 10 are: 1 10 2 5 
Divisors of 50 are: 1 50 2 25 5 10 
Divisors of 100 are: 1 100 2 50 4 25 5 20 10 

Method 3: Optimized Code with sorted result

In the previous method, results are produced in a irregular fashion (printed in pairs - small number and large number). The result can be sorted by storing the larger number and print them later on. Consider the example below:

import java.lang.Math;

public class MyClass {
  //method to print all divisors of a number
  static void printDivisors(int n) {
    System.out.print("Divisors of " + n + " are: ");
    
    //creating an array to store larger numbers
    int[] arr = new int[n];
    int j = 0;
    
    //loop from 1 to Math.sqrt(n)
    for(int i = 1; i <= Math.sqrt(n); i++) {
      if(n%i == 0) {
        if(n/i == i)
          System.out.print(i + " ");
        else {
          System.out.print(i + " ");
          //storing the large number of a pair
          arr[j++] = n/i;        
        }
      }
    }

    //printing stored large numbers of pairs
    for(int i = j - 1; i >= 0; i--)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  public static void main(String[] args) {
    printDivisors(10);
    printDivisors(50);
    printDivisors(100);
  }
}

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100 

Method 4: Another Optimized Code

To produce the result in sorted order, we can iterate from 1 to square root of n and printing the number which divides n. After that we can iterate back (in reverse order) and printing the quotient of all numbers which divides n.

import java.lang.Math;

public class MyClass {
  //method to print all divisors of a number
  static void printDivisors(int n) {
    System.out.print("Divisors of " + n + " are: ");
    //loop from 1 to Math.sqrt(n)
    int i;
    for(i = 1; i <= Math.sqrt(n); i++) {
      if(n%i == 0) 
        System.out.print(i + " ");
      
      //handing perfect squares
      if(n/i == i) {
        i--; break;
      }
    }

    for(; i >= 1; i--) {
      if(n%i == 0) 
        System.out.print(n/i + " ");
    }  
    System.out.println();
  }

  public static void main(String[] args) {
    printDivisors(10);
    printDivisors(50);
    printDivisors(100);
  }
}

The above code will give the following output:

Divisors of 10 are: 1 2 5 10 
Divisors of 50 are: 1 2 5 10 25 50 
Divisors of 100 are: 1 2 4 5 10 20 25 50 100