How to find factors of a number in java

What are factors of a number?
Factors of a number are integers that completely divide the number. Complete division means that the remainder of division is zero. Factors of a numbers are also called divisors.
Example, Consider the number 50. All integers that completely divide 50 are 1, 2, 5, 10, 25 and 50. These are called factors of 50.
This post will show you how to find all the factors of a number using java program.

Algorithm
Logic to find factors of a number consists of below steps.

1. Loop from 1 till the number.
2. In every iteration divide the number whose factors need to be determined by current loop counter and check the remainder of division
3. If the remainder is zero, then the current loop counter is a factor of given number else not.

Though this post implements this algorithm in java but once it is understood, the program can be written in any other language.
Java program
Java program to find factors of a number written as per above algorithm is given below.

import java.util.Scanner;

public class FactorCalculator {

   public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 System.out.println("Enter a number");
 // read number from keyboard
 int number = scanner.nextInt();
        // close scanner
 scanner.close();
 System.out.println("Factors of " + number + " are:");
 // iterate from 1 till the number
 for (int loopCounter = 1; loopCounter <= number; loopCounter++) {
  // check if remainder of division is 0
  if (number % loopCounter == 0) {
   System.out.print(loopCounter + " ");
  }
 }
   }
}

Above program reads number from user input from keyboard using java.util.Scanner class. It then iterates from 1 till the entered number using a for loop.

In every iteration, it divides the number with the current loop variable to check the remainder of division. Note that modulus operator(%) is used to determine the remainder of division.
If the remainder is zero, means the current loop counter is a factor of the number and is displayed otherwise loop moves to the next integer.

Note that the above program finds the factors of a number using for loop but it can also be modified to use while loop as well.
Output
Above program when executed produces the below result.

Time Complexity of this program is O(n).
Optimization
Although above program works well and determines all the factors of a number. But this solution can further be optimized by reducing its time complexity so that it is well suited for large numbers as well.
Above program iterates from 1 till the number itself which increases the time taken if the number is large.
Approach
All the factors of a number can be determined by iterating only till the square root of a number. This is because each factor of a number which is lesser than its square root when divided by the number gives another factor which is greater than the square root of number.
Example, consider 50. Its square root is 7.

Factors of 50 less than 7 are 1, 2 and 5. Each of these factors when divided by 50 will give factors which are greater than 7(square root of 50). That is, 50/1 = 50; 50/2 = 25 and 50/5 =10.
Thus, all the factors of 50 are 1, 2, 5, 50, 25 and 10.
This approach can be converted to a java program as given below.

import java.util.Scanner;

public class FactorCalculator {

   public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      System.out.println("Enter a number");
      // read number
      int number = scanner.nextInt();
      scanner.close();
      System.out.println("Factors of " + number + " are:");
      // iterate from 1 till square root of number
      for (int loopCounter = 1; loopCounter <= Math.sqrt(number); loopCounter++) {
         // check if remainder of division is 0
  if (number % loopCounter == 0) {    
            // print current factor and factor after square root        
            System.out.print(loopCounter + " " + number / loopCounter + " ");
  }
      }
   }
}

Loop iterates from 1 till the square root of the number. Square root is calculated using sqrt method of java.lang.Math class.

Notice how remainder of division of number with the loop variable is compared with 0. If it is 0, this means that the current loop counter is a factor of number and when divided by the number, it will determine another factor beyond the square root of the number.
Output
Above program prints following result.

Time complexity of this program is O(1) which is lesser than previous method.