If A and B are a

*integer of an***non-zero****integral domain**then it is said that:- A divides B.
- A is a divisor of B.
- or, B is a multiple of A.

and, this is written as A/B if there exists an integer K, such that AK = B.

**For Example,**8 is a divisor of 48 because 8 x 6 = 48, so it can be said that 48 is divisible by 8 or 48 is a multiple of 8.

Let us say that we are given a natural number N and we need to find it’s all divisors.

For Example:

- Divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24.
- Divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36.

**So how we can find this?**

**Method – 1**

**The Brute Force approach.**

Iterate a for loop from i = 1 to i = N and check the condition if N%i ==0** **and if this is true then i is a divisor of N.

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n = 1000000; // we will be finding all

// the divisor of 10^6 here.

vector<int> divisor;

for (int i = 1; i <= n; i++) {

if (n % i == 0) {

divisor.push_back(i);

}

}

for (auto c : divisor) {

cout << c << “ “;

}

cout << endl;

}

**The time complexity for the above approach is O(N).**

**But the above approach can work for N upto 10^6, what if N is 10^12? So let’s go for another method which can find all the divisors for these many big numbers efficiently.**

**Method – 2**

There is an efficient algorithm to find all the divisor in sqrt(N) time complexity.

**Claim:**

**Half of the divisors of N are less than Sqrt(N)**

For Example:

Divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24, out of which 1, 2, 3, 4 are less than Sqrt(24)

Divisors of 15 are 1, 3, 5, 15, out of which 1, 3 are less than Sqrt(15).

All the divisors are present in pairs look at the example below.

Divisors of 24 are (1, 24), (2, 12), (3, 8), (4, 6)

Divisors of 36 are (1, 36), (2, 18), (3, 12), (6, 6)

If we multiply the elements of each pair the value would be N. We, however, have to care if N is a perfect square because in this case, we’ll get two equal divisors.

## Proof of correctness

Let us take two divisor d1 and d2 such that 1 ≤ d1 ≤ Sqrt(N) and Sqrt(N) ≤ d2 ≤ N. So minimum valued divisor = 1 and maximum valued divisor = N.

Divisors of 24 are (1, 24), (2, 12), (3, 8), (4, 6)

Divisors of 36 are (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)

In the above example, we can see that pairs are in the form of (d1, N/d1). It means d2 = N/d1 (N divided by d1).

For divisors of 24, we can also write (1, 24/1), (2, 24/2), (3, 24/3), (4, 24/4). and 4 is less than or equal to Sqrt(N).

For Divisors of 36, we can also write (1, 36/1), (2, 36/8), (3. 36/3), (4, 36/4), (6, 36/6), and 6 is equal to sqrt(N).

**Here is the efficient algorithm to find all the divisors of a natural number in O(sqrt(N)) time complexity.**

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n = 1000000; // we will be finding all

// the divisor of 10^6 here.

vector<int> divisor;

for (int i = 1; i * i <= n; i++) {

if (n % i == 0) {

if (i == (n / i)) {

divisor.push_back(i);

} else {

divisor.push_back(i);

divisor.push_back(n / i);

}

}

}

for (auto c : divisor) {

cout << c << “ “;

}

cout << endl;

}

This is all for this article, if you find any error then do comment so that we can correct it and learn from it.

Thank you for Reading.

**Written with 💗 by Manish**