Find Proper Divisors of integer 'n'

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!

Find Proper Divisors of integer 'n'

Comments

Datastructures and Problem-Solving using Javascript

More from this blog

What is JavaScript and How It Powers Modern Websites

Project Euler: #17 - Number letter counts

Project Euler: #16 - Power digit sum

Project Euler: #15 - Lattice paths

Project Euler: #14 - Longest Collatz sequence

Problem: Divisors of 'n'

Approach

Brute force method:

Squareroot of n method:

Code

Command Palette

Comments

Datastructures and Problem-Solving using Javascript

More from this blog

Problem: Divisors of 'n'

Approach

Brute force method:

Squareroot of n method:

Code