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.

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.

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.

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.

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.

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

Never Miss an article !

Get the new post delivered straight into your inbox, enter your email and hit the button

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

codippa will use the information you provide on this form to be in touch with you and to provide updates and marketing.