Get this book -> Problems on Array: For Interviews and Competitive Programming

In this post, we discuss formulas for getting the number of divisors of a number and their sum, additionally we will implement an algorithm that solves this problem.

Table of contents:

- Problem statement
- Number of divisors
- Sum of divisors

## Problem statement

A * Composite number* is a number greater than 1 with more than two factors.

A * Divisor* is a number that divides another number either completely or with a remainder

So, given a number N, we have to find:

- Sum of Divisors of N
- Number of Divisors of N

# 1. Number of divisors

#### Examples.

n = 4, divisors are 1, 2, 4

n = 18, divisors are 1, 2, 3, 6, 9, 18

n = 36, divisors are 1, 2, 3, 4, 6, 9, 12, 18, 36

We need a formula to find the number of divisors of a composite number without computing the factors of that number.

* Fundamental theorem of arithmetic*.

The theorem States that every positive integer greater than 1 can be represented uniquely as a product of its primes not considering the arrangement of the prime factors.

Prime factorization 18

18 | |
---|---|

2 | 9 |

3 | 3 |

3 | 1 |

That is ${2}^{1}\xc2\xb7{3}^{2}$

Prime factoriazation 90

90 | |
---|---|

2 | 45 |

3 | 15 |

3 | 5 |

5 | 1 |

That is ${2}^{1}\xc2\xb7{3}^{2}\xc2\xb7{5}^{1}$

Notice that we get a unique prime factorization always if we do not change the order of the factors.

## Finding number of divisors

Assume n = 18

Let the prime factorization of n be,

$n=p{1}^{{\mathrm{\xce\pm}}_{1}}+p{2}^{{\mathrm{\xce\pm}}_{2}}+...+p{k}^{{\mathrm{\xce\pm}}_{k}}$

Number of divisors will be,

$divisors=({\mathrm{\xce\pm}}_{1}+1)\xc2\xb7({\mathrm{\xce\pm}}_{2}+1)\xc2\xb7...\xc2\xb7({\mathrm{\xce\pm}}_{k}+1)$

**Proof**

18 = ${2}^{1}\xc2\xb7{3}^{2}$.

Divisors of ${2}^{1}$ are ${2}^{1}$ and ${2}^{0}$ = 2.

Divisors of ${3}^{2}$ are ${3}^{2}$, ${3}^{1}$ and ${3}^{0}$ = 3.

Therefore the divisors of 18 are $({2}^{0}\xc2\xb7{3}^{0}),({2}^{0}\xc2\xb7{3}^{1}),({2}^{0}\xc2\xb7{3}^{2}),({2}^{1}\xc2\xb7{3}^{0}),({2}^{1}\xc2\xb7{3}^{1}),({2}^{1}\xc2\xb7{3}^{2})$ making a total of 6 divisors which is 3 * 2.

## Naive Approach

In this approach we would iterate over all the numbers from 1 to the square root of n checking the divisibility of an element to n while keeping count of the number of divisors.

### Analysis

The time complexity is proportional to the square root of n, that is $O\left(\sqrt{n}\right)$.

The space complexity is constant O(1), no extra space is needed.

### Optimal Approach

In this optimized solution we will try to reduce the $O\left(\sqrt{n}\right)$ complexity to $O\left({n}^{\frac{1}{3}}\right)$ time complexity.

We write n as a product of 3 numbers, p, q, r that is p * q * r = N where p <= q <= r hence the maximum value for p is ${N}^{\frac{1}{3}}$.

We now loop over all prime numbers in the range of [2, ${N}^{\frac{1}{3}}$] and try to reduce n to its prime factorization while counting the number of factors of n.

We split n into two number x and y such that x * y = n.

x contains prime factors in range of [2, ${N}^{\frac{1}{3}}$] and y deals with larger prime factors (> ${N}^{\frac{1}{3}}$).

Thus the gcd of x,y is 1.

We let count of divisors be a function f(n).

f(mn) = f(m) * f(n) if gcd(m, n) == 1

Therefore if we can find f(x) and f(y), we can also find f(x * y) which is the required number of divisors.

**finding f(x)**

Here we use division to prime factorize x and calculate the number of factors. After this procedure we will remain with y=$\frac{n}{x}$ which is to be factorized.

Possibilities of y are,

- Y is prime number f(y) = 2
- y is a square of a prime number f(y) = 3
- y is a product of two distinct prime numbers f(y) = 4

If we found f(x) and f(y) we are done because f(n) = f(x * y);

### Pseudocode

```
N is input.
initialize primes array to store primes up to 10^6.
initialize result to 1
for all p in primes:
if p*p*p > N:
break;
count = 1
while N is divisible by p:
N = N / p
count += 1
result = result * count
if N is prime:
result = result * 2
else if N is square of a prime:
result = result * 3
else if N is not equal to 1
result = result * 4
```

#### Code: (naive approach included)

```
#include<iostream>
#include<cmath>
using std::cout;
using std::cin;
using std::endl;
typedef long long ll;
class Divisors{
private:
void eratosthenesSieve(ll n, bool prime[], bool primeSquare[], ll arr[]){
//boolean array with true entries
for(int i = 2; i <= n; i++)
prime[i] = true;
//boolean array with false entries
for(int i = 0; i <= (n*n+1); i++)
primeSquare[i] = false;
prime[1] = false;
for(int p = 2; p*p <= n; p++){
if(prime[p] == true){
//update multiples of p from p*p
for(int i = p*p; i <= n; i+= p)
prime[i] = false;
}
}
ll j = 0;
for(int p = 2; p <= n; p++){
if(prime[p]){
arr[j] = p;
//if p is prime, update value in primesquare array
primeSquare[p*p] = true;
j++;
}
}
}
public:
//naive approach
ll numDivisorsNaive(ll n){
int count = 0;
for(int i = 1; i <= sqrt(n); i++){
//if divisible
if(n % i == 0){
//if equal divisors, increment count by 1
if(n / i == i)
count++;
else
//not equal divisors, increment count twice
count += 2;
}
}
return count;
}
//efficient approach using sieve
ll numDivisorsOptimal(ll n){
//1 factor
if(n == 1)
return 1;
//init prime and primesquares arrays
bool prime[n+1], primeSquare[n*n+1];
//store primes
ll arr[n];
//store results in prime and primesqaures arrays
eratosthenesSieve(n, prime, primeSquare, arr);
//count distinct divisors
ll res = 1;
for(int i = 0;; i++){
//terminates loop if condition is encountered
if(arr[i] * arr[i] * arr[i] > n)
break;
int count = 1;
while(n % arr[i] == 0){
n = n / arr[i];
//increment power
count = count + 1;
}
//if n = a^p * b^q, total divisors are (p+1)*(q+1)
res = res * count;
}
//loop terminates
//check cases
if(prime[n])
res = res * 2;
else if(primeSquare[n])
res = res * 3;
else if(n != 1)
res = res * 4;
return res;
}
};
int main(){
Divisors div;
long long n;
cout << "num " << endl;
cin >> n;
cout << "Number of divisors: " << div.numDivisorsNaive(n) << endl;
cout << "Number of divisors: " << div.numDivisorsOptimal(n) << endl;
return 0;
}
```

* Note:* In the above implementation we used Sieve of Eratosthenes which is an algorithm for finding primes up to a given limit.

In large datasets > 500k we may use miller-rabin's primality test to check for primes which will be more efficient.

## Time and Space Complexity Analysis

We check primality using Sieve of Eratosthenes whose time complexity is O(n log log n) for 3 cases, total time complexity is $O\left({n}^{\frac{1}{3}}\right)$.

The space complexity is and O(n).

# 2. Sum of divisors

We shall use the previous example of n = 18.

We have the following divisors

$({2}^{0}\xc2\xb7{3}^{0}),({2}^{0}\xc2\xb7{3}^{1}),({2}^{0}\xc2\xb7{3}^{2}),({2}^{1}\xc2\xb7{3}^{0}),({2}^{1}\xc2\xb7{3}^{1}),({2}^{1}\xc2\xb7{3}^{2})$.

Which is the same as $({2}^{0}+{2}^{1})\xc2\xb7({3}^{0}+{3}^{1}+{3}^{2})$.

The above is a geometric progression.

The geometric progression formula is $\frac{a({r}^{n}-1)}{r-1}$.

Where *a = first term*, *r = common ratio*, *n = number of terms*.

Therefore the sum of divisors is $\frac{1({2}^{2}-1)}{2-1}\xc2\xb7\frac{1({3}^{3}-1)}{3-1}=39$

### Naive approach

In this approach we would iterate over all the numbers from 1 to the square root of n checking the divisibility of an element and add it to a variable result which we would return when the loop terminates.

### Code

```
#include<iostream>
#include<cmath>
using std::cout;
using std::cin;
using std::endl;
typedef long long ll;
ll sumDivisors(ll n){
int sumDivisors = 0;
if(n == 1)
return sumDivisors;
//iterate looking for numbers than can divide n
for(int i = 2; i <= sqrt(n); i++){
if(n % i == 0){
//add once of divisors are same
if(i == (n / i))
sumDivisors += i;
else
//add once
sumDivisors += (i + n / i);
}
}
//add 1, loop starts at 2 and add n
return sumDivisors+1+n;
}
int main(){
long long n;
cout << "num ", cin >> n;
cout << "Sum of divisors: " << sumDivisors(n) << endl;
return 0;
}
```

### Analysis

The time complexity is proportional to the square root n, $O\left(n\sqrt{n}\right)$.

The space complexity is O(1) constant space.

### Optimized approach

In this optimal approach we use Sieve of Eratosthenes algorithm for finding the prime factors and implement an algorithm that solves the problem in (logn) time for n using prime factors generated by the sieve algorithm.

```
#include<iostream>
#include<vector>
#include<bitset>
#include<cmath>
using std::vector;
using std::bitset;
using std::cout;
using std::cin;
using std::endl;
#define N 10000000
typedef long long ll;
class SumDivisors{
private:
bitset<N+10> flag;
vector<ll> p;
void eratosthenesSieve(){
p.push_back(2);
for(ll i = 3; i <= N; i+=2){
if(flag[i] == 0){
p.push_back(i);
if(i*i <= N){
for(ll j = i*i; j <= N; j += i*2){
flag[j] = 1;
}
}
}
}
}
ll sumDivisors(ll n){
ll result = 1;
for(ll i = 0; p[i]*p[i] <= n; i++){
if(n % p[i] == 0){
ll count = 1;
while(n % p[i] == 0){
n = n / p[i];
count += 1;
}
result *= (pow(p[i], count) - 1) / (p[i] - 1);
}
}
if(n > 1)
result *= (pow(n, 2) - 1) / (n - 1);
return result;
}
public:
void run(){
int n;
cout << "num : ", cin >> n;
eratosthenesSieve();
cout << sumDivisors(n) << endl;
}
};
int main(){
SumDivisors sd;
sd.run();
}
```

### Time and Space Complexity Analysis

Sieve of Eratosthenes will find powers in O(nlog(log(n))) time for a integer n. The sumDivisors algorithm works in O(logn) time after the vector is filled. Therefore the total time complexity is O(nlog(log(n)) which is better than $O\left(n\sqrt{n}\right)$.

The space complexity if O(n), we use extra space to store the prime factors of n.

* Note:* This is a good case of a trade off between space and time complexity, We degraded the previous constant space complexity to achieve a better time complexity.

With this article at OpenGenus, you must have the complete idea of finding Sum and Number of Divisors of a Number.