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
Recommended Pages
- Java Program - To Check Prime Number
- Java Program - Bubble Sort
- Java Program - Selection Sort
- Java Program - Maximum Subarray Sum
- Java Program - Reverse digits of a given Integer
- Java Program - Merge Sort
- Java Program - Shell Sort
- Stack in Java
- Queue in Java
- Java Program - Find LCM of Two Numbers
- Java Program - To Check Whether a Number is Palindrome or Not
- Java Program - To Check Whether a String is Palindrome or Not
- Java Program - Heap Sort
- Java Program - Quick Sort
- Java - Swap Two Numbers without using Temporary Variable
- Java Program - To Check Armstrong Number
- Java Program - Counting Sort
- Java Program - Radix Sort
- Java Program - Find Largest Number among Three Numbers
- Java Program - Print Floyd's Triangle