×

Search anything:

# Sum and Number of Divisors of a Number

#### Algorithms List of Mathematical Algorithms

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.

1. Problem statement
2. Number of divisors
3. 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}·{3}^{2}$

Prime factoriazation 90

90
2 45
3 15
3 5
5 1

That is ${2}^{1}·{3}^{2}·{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}^{{\alpha }_{1}}+p{2}^{{\alpha }_{2}}+...+p{k}^{{\alpha }_{k}}$

Number of divisors will be,
$divisors=\left({\alpha }_{1}+1\right)·\left({\alpha }_{2}+1\right)·...·\left({\alpha }_{k}+1\right)$

Proof

18 = ${2}^{1}·{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 $\left({2}^{0}·{3}^{0}\right),\left({2}^{0}·{3}^{1}\right),\left({2}^{0}·{3}^{2}\right),\left({2}^{1}·{3}^{0}\right),\left({2}^{1}·{3}^{1}\right),\left({2}^{1}·{3}^{2}\right)$ 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,

1. Y is prime number f(y) = 2
2. y is a square of a prime number f(y) = 3
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
$\left({2}^{0}·{3}^{0}\right),\left({2}^{0}·{3}^{1}\right),\left({2}^{0}·{3}^{2}\right),\left({2}^{1}·{3}^{0}\right),\left({2}^{1}·{3}^{1}\right),\left({2}^{1}·{3}^{2}\right)$.
Which is the same as $\left({2}^{0}+{2}^{1}\right)·\left({3}^{0}+{3}^{1}+{3}^{2}\right)$.

The above is a geometric progression.

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

Where a = first term, r = common ratio, n = number of terms.
Therefore the sum of divisors is $\frac{1\left({2}^{2}-1\right)}{2-1}·\frac{1\left({3}^{3}-1\right)}{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
sumDivisors += (i + n / i);
}
}
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.

#### Erick Lumunge

Erick Lumunge is a passionate programmer with a computer science background who loves to learn about and use code to impact lives positively.

Sum and Number of Divisors of a Number