Program to Find Factors of a Number in Java

Java Program to Find Factors of a Number | A number which divides completely the number “N” is called the factor of the number “N”. For example:- the numbers 1, 2, 3, 4, 6 and 12 are complete divides the number 12 so they are called the factor of 12. Completly divisible means when we divide the number then it gives result zero.

The number which has only two factors 1 and itself, those numbers are called the prime number. The numbers which have more than two factors are called composite numbers.

To find the factor of a positive number “N” divide that number using natural numbers 1 to “N”. If the number is divisible by the natural number then that natural number is the factor. A number N can have factors only in between 1 to N.

Steps to find the factors of a number:-
1) Take a number N as input
2) Take an iterator variable and initialize it with 1
3) Dividing the number N with an iterator variable
4) If it is divisible then it is a factor of the given number N
5) Increase the iterator variable
6) Repeat the 4 and 5 steps until the iterator variable becomes equal to N.

Java Program to find factors of a number

import java.util.Scanner;

public class Number {

   public static void findFactor(int n) {
       for(int i=1; i <= n; i++) {
           if(n % i == 0)
               System.out.print(i+"\t");
       }
   }

   public static void main(String[] args) {

       // declare variable
       int number = 0;

       // create Scanner class object
       Scanner scan = new Scanner(System.in);

       // take input
       System.out.print("Enter a number:: ");
       number = scan.nextInt();

       // find the factor of the number 
       System.out.print("The factors are:: ");
       findFactor(number);

       // close Scanner class object
       scan.close();

   }
}

Output:-

Enter a number:: 12
The factors are:: 1 2 3 4 6 12

Enter a number:: 7
The factors are:: 1 7

The time complexity of this program is O(n).

In the findFactor() method we have used for loop. But we can also use the while loop, do-while.

Finding factors in Java using while loop

public static void findFactor(int n) {
    int i = 1;
    while (i <= n) {
        if(n % i == 0) 
        System.out.print(i+"\t");
        i++;
    }
}

Finding factors in Java using do-while loop

public static void findFactor(int n) {
    int i = 1;
    do {
        if(n % i == 0) 
        System.out.print(i+"\t");
        i++;
    } while (i <= n);
}

In the above methods for a number “N” the loop iterates n times. Hence, the time complexity of the program is O(n). In simple words, If we want to find the factors of the number 20 then the loop iterates 20 times. For large numbers like 45826752, it will take a long time to execute the program. Hence the above program less performance.

Optimization

We have seen that the above program works fine and gives the correct result but it gives less performance. Can we increase the performance by decreasing the number of iterations?

The factors of a number can be determined by iterating only till the square root value of that number because each factor of a number which is lesser than its square root can give the remaining factors which are greater than the square root of the number by dividing the number.

Example:-
Assume that we are finding the factors of number 24.
The square root of the number is 4.8.
The factors less than equal to 4.8 are 1, 2, 3, and 4.
The remaining factors can be calculated as dividing number 24 by factors 1, 2, 3, and 4
24/1 = 24, 24/2 = 12, 24/3 = 8, and 24/4 = 6
So finally the factors of 24 are:- 1, 2, 3, 4, 6, 8, 12, and 24

To find the square root of the number we can take the help of the sqrt() function which is defined as the Math class.

public static void findFactor(int n) {
   for(int i=1; i <= Math.sqrt(n); i++) {
       if(n % i == 0) 
       System.out.print(i+"\t"+ (n/i) +"\t");
   }
}

Output:-

Enter a number:: 24
The factors are:: 1 24 2 12 3 8 4 6

Enter a number:: 20
The factors are:: 1 20 2 10 4 5

The output is not in ascending order, but it gives better performance compared to the previous program. For the number 24, the previous methods iterate 24 times but now the above method can iterate only 4 times. Now, the time complexity of this program is O(1).

Problem with the above method

When we try to find the factor of the number having perfect square then the above method displays those factors 2 times.

Sample Input/Output:-

Enter a number:: 36
The factors are:: 1 36 2 18 3 12 4 9 6 6

Enter a number:: 9
The factors are:: 1 9 3 3

We should not display the same factor for two times. So, we can use the if-else statement and stop displaying the same factor two times.

public static void findFactor(int n) {
   for(int i=1; i <= Math.sqrt(n); i++) {
      if(n % i == 0) {
          System.out.print(i+"\t");
            if(n/i != Math.sqrt(n) )
            System.out.print((n/i)+"\t");
       }
   }
}

Output for different test-cases:-

Enter a number:: 9
The factors are:: 1 9 3

Enter a number:: 16
The factors are:: 1 16 2 8 4