**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.

- Loop from 1 till the number.
- In every iteration divide the number whose factors need to be determined by current loop counter and check the remainder of division
- 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.

Learn how to read user input from keyboard using different methods in java **here**.

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.

`while`

loop as well.**Output**

Above program when executed produces the below result.

Enter a number

50

Factors of 50 are:

1 2 5 10 25 50

**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.

**Output**

Above program prints following result.

Enter a number

100

Factors of 100 are:

1 100 2 50 4 25 5 20 10

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

1