Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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} \cdot 3^{2}$

Prime factoriazation 90

	90
2	45
3	15
3	5
5	1

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

Number of divisors will be,
$d i v i s o r s = (α_{1} + 1) \cdot (α_{2} + 1) \cdot . . . \cdot (α_{k} + 1)$

Proof

18 = $2^{1} \cdot 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} \cdot 3^{0}), (2^{0} \cdot 3^{1}), (2^{0} \cdot 3^{2}), (2^{1} \cdot 3^{0}), (2^{1} \cdot 3^{1}), (2^{1} \cdot 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 (\sqrt{n})$ .
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 (\sqrt{n})$ complexity to $O (n^{\frac{1}{3}})$ 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 (n^{\frac{1}{3}})$ .

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} \cdot 3^{0}), (2^{0} \cdot 3^{1}), (2^{0} \cdot 3^{2}), (2^{1} \cdot 3^{0}), (2^{1} \cdot 3^{1}), (2^{1} \cdot 3^{2})$ .
Which is the same as $(2^{0} + 2^{1}) \cdot (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} \cdot \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 (n \sqrt{n})$ .
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 (n \sqrt{n})$ .

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.

Sum and Number of Divisors of a Number

Algorithms List of Mathematical Algorithms

Problem statement

1. Number of divisors

Examples.

Finding number of divisors

Naive Approach

Analysis

Optimal Approach

Pseudocode

Code: (naive approach included)

Time and Space Complexity Analysis

2. Sum of divisors

Naive approach

Code

Analysis

Optimized approach

Time and Space Complexity Analysis

3 Sum Smaller Problem

Time and Space Complexity of Interpolation Search