Problem: Divisors of 'n'
Given a positive integer n
. Find all the proper divisors of the integer n
.
Approach
We can approach this in two ways.
Brute force method
Squareroot of n method
Brute force method:
The most basic approach is to apply the brute force method. Brute force solves a problem through exhaustion. It goes through all possible choices until a solution is found.
To find the divisors for a positive integer n
, we iterate all the integers from 1, 2, 3, . . . , n
, and divide n
by each of those integers i
, and those that divide evenly make up the set of divisors for n
.
This is rather plain, easy and simple but is not quite an efficient solution.
The time complexity to find divisors of n
is O(n)
.
Consider that we need to find the divisors of the number 100000
. Then using the brute force method, we divide 100000
by 1 to 100000
taking 100000
iterations. This would take a long time to compute all the divisors of 100000
.
So to solve this problem, we can use a more efficient solution like that of Squareroot of n
method
Squareroot of n method:
Let us observe the divisors of 100
first as an example.
The proper divisors of 100
are 1, 2, 4, 5, 10, 20, 25, and 50
which can be written as 1, 2, 4, 5, 10, 100/5, 100/4, and 100/2
.
If i
is a divisor of n
, then d = n/i
is also a divisor of n
because i * d = n
. Hence the divisors can be organised into pairs of (i, d) = (i, n/i)
. The exception for this is if n
is a perfect square and i = sqrt(n)
, then in this case both i
and d
are equal.
Thus the divisors of a number n
usually, appear in pairs and using this method, the time complexity is O(sqrt(n))
For finding divisors of 100
, it involves 10
iterations and for 100000
, it takes roughly 316
iterations.
Example of finding divisors of n = 100
(Code given below)
Code
const properDivisors = n => {
let divisors = [1];
// Condition can either be `i <= sqrt(n)` OR `i * i <= n`. Both are equivalent.
// if square of `i` = `n`, then always square root of `n` = `i`
for (let i = 2; i * i <= n; i++) {
if (n % i === 0) {
divisors.push(i, n / i);
if (i === Math.sqrt(n)) { // Condition can either be `i === sqrt(n)` OR `i * i === n`. Both are equivalent.
divisors.pop();
}
}
}
return divisors.sort(function (a, b) { return a - b; });
}
console.log(properDivisors(100)); // 1,2,4,5,10,20,25,50
console.log(properDivisors(144)); // 1,2,3,4,6,8,9,12,16,18,24,36,48,72
You can find my solution here at ProperDivisors
I hope you learn something new and enjoy coding. If you have any feedback, please leave it below.
If you have any suggestions to improve my code or another way to approach this problem, leave it in the comment.
Thanks & Happy Coding!