Given a number n, print all distinct divisors of it , including 1 and the number itself.
Example:
Input: n=20
output: 1 2 4 5 10 20
input n=125
output: 1 5 25 125
Method 1: A solution would be to iterate all the number from 1 to n, checking if that number divides n and print it.
Method 2: A solution would be to iterate all the number from 1 to square root of n, checking if that number divides n and print the number pair if number pair are equal then print only one. It print the divisors in small-big pair.
Method 3: A solution would be to iterate all the number from 1 to square root of n, checking if that number divides n and print the first number and store the second number in a list if number pair are equal then print only one and print the list in reverse order. It print the divisors in sorted order.
Below is a java program for the same.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
/**
* Created by Sani Kamal on 29-May-17.
*/
//Java program to find all divisors of a natural number including
// 1 and the number itself
public class PrintDivisors {
//Method to print all divisors
//Time complexity: O(n)
//Auxiliary Space= O(1)
//It prints divisors in sorted order
private static void printDivisorAsc(int number) {
for (int i = 1; i <= number; i++) {
if (number % i == 0) {
System.out.print(i + " ");
}
}
}
//Method to print all divisors
//Time complexity: O(log(n))
//Auxiliary Space= O(1)
//it prints divisors in random order
private static void printDivisorRand(int number) {
//This loop run till square root
for (int i = 1; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
//If divisors are equal, print only one
if (number / i == i) {
System.out.print(i + " ");
}
//otherwise print both
else {
System.out.print(i + " " + number / i + " ");
}
}
}
}
//Method to print all divisors,it prints divisors in sorted order
//Time complexity: O(log(n))
//Auxiliary Space= O(1)
private static void printDivisorSorted(int number) {
List li=new ArrayList<Integer>();
//This loop run till square root
for (int i = 1; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
//If divisors are equal, print only one
if (number / i == i) {
System.out.print(i + " ");
}
else {
System.out.print(i + " ");
// add the second divisor in list
li.add(number/i);
}
}
}
//The list will print reverse
for (int i = li.size()-1; i >=0 ; i--) {
System.out.print(li.get(i)+" ");
}
}
//Driver program to test above method
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter a number to find divisors:");
try {
int num = Integer.parseInt(br.readLine());
printDivisorAsc(num);
System.out.println();
printDivisorRand(num);
System.out.println();
printDivisorSorted(num);
} catch (Exception e) {
System.out.println(e.getMessage());
e.printStackTrace();
}
}
}
Output
"C:\Program Files\Java\jdk1.8.0_65\bin\java"
Enter a number to find divisors:
124
1 2 4 31 62 124
1 124 2 62 4 31
1 2 4 31 62 124
Process finished with exit code 0
hellotech 