# 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)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1673398434971/1907c2e9-1d21-4f59-9df3-8dbdcda1ab5e.png align="center")

## Code

```javascript
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](https://github.com/sansk/datastructures-and-problem-solving-javascript/tree/main/01-Basic/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!