Last Updated: 15 Jul, 2022
Find all Divisors of a natural number
Easy
You are given a natural number ‘N’. Find all the divisors of the number ‘N’. Print them in increasing order.
Example:
Input: ‘N’ = 10
Output: [1, 2, 5, 10]
1, 2, 5, and 10 are the only divisors of the number 10.
Input Format :
The first line will contain the integer 'T', denoting the number of test cases.
The first line of each test case contains a natural number ‘N’.
Output format :
For each test case, you don’t need to print anything just return a sorted array containing all the divisors of ‘N’.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^9
Time Limit: 1 sec
Approaches
In this approach, We can iterate over all the numbers from 1 to ‘N’ and check if ‘N’ is divisible by that number or not. If it is divisible we can store it in an array. Since we are iterating from 1 to ‘N’ the divisors will be stored in the array in increasing order.
The steps are as follows:-
function getAllDivisors( int n ):
- Declare an array 'ANS' to store all the divisors of 'N' in increasing order.
- Iterate over all the numbers from 1 to 'N', for 'i'=1...'N':
- If 'N' is divisible by 'i' then push it into the 'ANS' array.
- Return the array 'ANS'.
If we observe the divisors of any number ‘N’, the divisor can be written as pairs like (‘X’, ‘Y’) where ‘X’ <= ‘Y’ and ‘N’ / ‘X’ = ‘Y’.
For example divisors of 100 can be written as (1, 100), (2, 50), (4, 25), (5, 20), (10, 10). So we can just iterate from 1 to the square root of ‘N’ and check if the number is a divisor of ‘N’ or not, if it is a divisor and let the number be ‘X’ then ‘X’ and ‘N’ / ‘X’ will be new divisors.
One thing to note is that if (‘X’ and ‘N’ / ‘X’) are equal then we use only one of them. To print the answer in sorted order, at first from every pair (‘X’, ‘N’ / ‘X’) store only ‘X’ in the array and then traverse the array in reverse order then append ‘N’ / ‘X’ to the back of the array.
The steps are as follows:-
Function getAllDivisors(int n):
- Declare an array 'ANS' to store all the divisors of 'N' in increasing order.
- Iterate over all the numbers from 1 to the square root of 'N', for 'i'=1...sqrt('N'):
- If 'N' is divisible by 'i' then push it into the 'ANS' array.
- Declare a variable 'curLen' to store the current length of the 'ANS' array.
- Run a loop from 'i' = 'curLen' - 1...0:
- Initialize a variable 'newDivisor' with value 'N' / ANS[ i ]'.
- If 'newDivisor' is not equal to ‘ANS[ i ]' then push it into the back of the 'ANS' array
- Return the array 'ANS'.