How to find the number of divisors and sum of divisors of a number

Gorakhnath yadav
Last Updated: May 13, 2022

Introduction

Finding the number of divisors and the sum of divisors of a number is a very important concept for programming. Even though it is easy to find the number of divisors and the sum of divisors of a number if it is small, finding the number and sum of divisors of a large number will be difficult. 

So let's first begin with finding the number of divisors of a number, then we will learn about finding the sum of divisors of a number.

The number of divisors of a number

To find the number of divisors of a number, we start by finding the prime factorization of the number, as all the divisors of a number will be a subset of the number's prime factorization. In simple words, if we can devise a way to find all the subset of prime factorizations of a number, we can find the number of divisors of that number. 

Let's say we have a number with x terms in its prime factorization. Then to find the total number of divisors of this number, we will have to find the total number of ways to select any number of terms from these x terms or the total number of subsets of x. It would have been easier because the total number of subsets of a set is 2no. Of elements in the set, but here the x might have some repeated terms. So we first find the prime factorization of a number, then represent the number in terms of distinct prime factors. For example- we can represent 36 as 22.32

Now, suppose we have a number F which appears p times in the prime factorization of a number X, then it can appear in subsets in p+1 ways, i.e.,{"font":{"family":"Arial","size":11,"color":"#000000"},"aid":null,"type":"$$","id":"2-0","backgroundColorModified":false,"code":"$$F^{0},F^{1},F^{2}......F^{P-2},F^{P-1},F^{P}$$","backgroundColor":"#ffffff","ts":1634311174194,"cs":"1oDSZJe089P8QVPhWViB+g==","size":{"width":240,"height":17}}

 

So, for a number, {"backgroundColorModified":false,"code":"$$Y=F_{1}^{p^{1}}.F_{2}^{p^{2}}.F_{3}^{p^{3}}.....F_{x-2}^{p^{X-2}}.F_{x-1}^{p^{X-1}}.F_{x}^{p^{X}}$$","id":"1-0-0-0","type":"$$","aid":null,"backgroundColor":"#ffffff","font":{"family":"Arial","size":11,"color":"#000000"},"ts":1634311026878,"cs":"xoCyYWV1FOow8K5ptpbkzA==","size":{"width":288,"height":24}}We can say that each distinct factor Fhas Pi+1 ways to appear in subsets. So the total number of divisors of a number Y={"backgroundColor":"#ffffff","id":"3","aid":null,"backgroundColorModified":null,"type":"$$","code":"$$\\left(P^{1}+1\\right)\\left(P^{2}+1\\right)\\left(P^{3}+1\\right).......\\left(P^{X-2}+1\\right)\\left(P^{X-1}+1\\right)\\left(P^{X}+1\\right)$$","font":{"color":"#000000","size":11,"family":"Arial"},"ts":1634312338862,"cs":"hEIc1P/N+WCIpkRMbBoLng==","size":{"width":489,"height":20}}

 

The sum of divisors of a number

To find the sum of all the divisors of a number, we will start with the formulae we used to find the number of divisors.

As we know, if a number F appears p times in the prime factorization of a number X, it can appear in subsets in p+1 ways, i.e.,{"font":{"family":"Arial","size":11,"color":"#000000"},"aid":null,"type":"$$","id":"2-1","backgroundColorModified":false,"code":"$$F^{0},F^{1},F^{2}......F^{P-2},F^{P-1},F^{P}$$","backgroundColor":"#ffffff","ts":1634311174194,"cs":"9OP3xCzQHks7n4D0maui/Q==","size":{"width":240,"height":17}} Now, if we multiply the set of choices of each factor, we will get a set of all possible divisors. 

For example, if we have a number with two factors, then all the terms in the product   {"aid":null,"code":"$$\\left(F_{1}^{0},F_{1}^{1},......F_{1}^{P^{1}-1},F_{1}^{P^{1}}\\right).\\left(F_{2}^{0},F_{2}^{1},......F_{2}^{P^{2}-1},F_{2}^{P^{2}}\\right)$$","font":{"color":"#000000","family":"Arial","size":11},"backgroundColor":"#ffffff","type":"$$","backgroundColorModified":false,"id":"2-2","ts":1634322930145,"cs":"6vDh3pYdrFguq0ETR3hN3g==","size":{"width":412,"height":30}}will form the set containing all the divisors. 

Since we need the sum of all the divisors of a number, we will find the product of the sum of all the choices for each factor. For the above example- the  {"id":"5-0-0","aid":null,"type":"$$","code":"$$\\left(F_{1}^{0}+F_{1}^{1}+......F_{1}^{P^{1}-1}+F_{1}^{P^{1}}\\right).\\left(F_{2}^{0}+F_{2}^{1}+......F_{2}^{P^{2}-1}+F_{2}^{P^{2}}\\right)$$","font":{"family":"Arial","size":11,"color":"#000000"},"backgroundColorModified":false,"backgroundColor":"#ffffff","ts":1634322977484,"cs":"V7KEZj7Fo5i/FwgebEPZ+g==","size":{"width":476,"height":30}}will represent the sum of all the divisors of a number. 

So, for any number, {"backgroundColorModified":false,"code":"$$Y=F_{1}^{p^{1}}.F_{2}^{p^{2}}.F_{3}^{p^{3}}.....F_{x-2}^{p^{X-2}}.F_{x-1}^{p^{X-1}}.F_{x}^{p^{X}}$$","id":"1-0-0-0","type":"$$","aid":null,"backgroundColor":"#ffffff","font":{"family":"Arial","size":11,"color":"#000000"},"ts":1634311026878,"cs":"xoCyYWV1FOow8K5ptpbkzA==","size":{"width":288,"height":24}}the sum of all the divisors of a number will be {"font":{"color":"#000000","size":11,"family":"Arial"},"type":"$$","id":"5-0-1","backgroundColor":"#ffffff","backgroundColorModified":false,"aid":null,"code":"$$\\left(F_{1}^{0}+F_{1}^{1}+......F_{1}^{P^{1}-1}+F_{1}^{P^{1}}\\right).\\left(F_{2}^{0}+F_{2}^{1}+......F_{2}^{P^{2}-1}+F_{2}^{P^{2}}\\right)......\\left(F_{x-1}^{0}+F_{x-1}^{1}+......F_{x-1}^{P^{x-1}-1}+F_{x-1}^{P^{x-1}}\\right).\\left(F_{x}^{0}+F_{x}^{1}+......F_{x}^{P^{x}-1}+F_{x}^{P^{x^{}}}\\right)$$","ts":1634323244326,"cs":"eVf884e0NPAf5+WFFJFnwA==","size":{"width":1054,"height":30}}

 

In this expression, we can observe that each term in the product is a GP. and for any GP, the sum of all the terms is {"font":{"family":"Arial","size":12,"color":"#000000"},"backgroundColor":"#ffffff","aid":null,"type":"$$","backgroundColorModified":null,"code":"$$\\left(\\left(First\\,term\\right)^{no.\\,of\\,terms\\,in\\,the\\,series}-1\\right)/\\left(First\\,term-1\\right)$$","id":"6-0","ts":1634323898956,"cs":"MPVNoVoLsZ6Dzdzsk9npcQ==","size":{"width":445,"height":33}}

Using this for every term in the formula {"font":{"color":"#000000","size":11,"family":"Arial"},"type":"$$","id":"5-0-1","backgroundColor":"#ffffff","backgroundColorModified":false,"aid":null,"code":"$$\\left(F_{1}^{0}+F_{1}^{1}+......F_{1}^{P^{1}-1}+F_{1}^{P^{1}}\\right).\\left(F_{2}^{0}+F_{2}^{1}+......F_{2}^{P^{2}-1}+F_{2}^{P^{2}}\\right)......\\left(F_{x-1}^{0}+F_{x-1}^{1}+......F_{x-1}^{P^{x-1}-1}+F_{x-1}^{P^{x-1}}\\right).\\left(F_{x}^{0}+F_{x}^{1}+......F_{x}^{P^{x}-1}+F_{x}^{P^{x^{}}}\\right)$$","ts":1634323244326,"cs":"eVf884e0NPAf5+WFFJFnwA==","size":{"width":1054,"height":30}}

We will get the result as-{"backgroundColor":"#ffffff","aid":null,"id":"6-1","type":"$$","code":"$$\\left(\\left(\\left(F_{1}\\right)^{P^{1+1}}-1\\right)/\\left(F_{1}-1\\right)\\right).\\left(\\left(\\left(F_{2}\\right)^{P^{2}+1}-1\\right)/\\left(F_{2}-1\\right)\\right).....\\left(\\left(\\left(F_{3}\\right)^{P^{3+1}}-1\\right)/\\left(F_{3}-1\\right)\\right).\\left(\\left(\\left(F_{4}\\right)^{P^{4}+1}-1\\right)/\\left(F_{4}-1\\right)\\right)$$","backgroundColorModified":false,"font":{"family":"Arial","color":"#000000","size":11.5},"ts":1634325209209,"cs":"vVsTGUk/LyET1RiHNeLK1w==","size":{"width":888,"height":32}}

Frequently Asked Questions 

  1. How can you find the total no. of divisors of a number?
    To find the total number of divisors of a number, we first find the prime factorization of the number and then find each distinct prime number's exponents. Then we add one to all the exponents and then find their product. The product is the number of divisors of a number. 
     
  2. What is the multiplicative identity?
    Multiplicative identity states that the product of any number with 1 is the number itself. Thus, we can also say that one is a divisor of every number.
     
  3. How do you find the number of odd divisors of a number?
    To find the number of odd divisors of a number, we first find the prime factorization of the number and then find each distinct prime number's exponents. Now, we remove even prime numbers in it. Then we add one to all the exponents of odd prime numbers and then find their product. The product is the number of odd divisors of a number.
     
  4. How do you find the number of odd divisors of a number?
    Since we know how to find the total number of divisors of a number and odd divisors of a number, the difference of both will be the even divisors of a number.
     
  5. What are the proper divisors of a number?
    The proper divisors of a number refer to the divisors, which are smaller than the number itself.

Key takeaways

In this blog, we have learned the formula for the number of divisors of a number and the sum of divisors of a number-

  • We learned about the formula to find the number of divisors of a number because any divisor of a number will be formed by selecting some factors from the prime factorization of the number. Then we found that the number of choices for each factor in forming another divisor is one more than the number of times it appears in the prime factorization of the number. Thus, the total number of choices for each factor gives us the total number of divisors of a number.
  • Then we learned about the formula to find the sum of divisors of a number using the similar concept we used for finding the number of divisors of a number. Since the product of all the choices for each factor for forming a divisor gives the total number of divisors. So, we find the product of the sum of the total number of choices for each distinct factor in the prime factorization of the number, which gives us the sum of all the number's divisors.

Visit here to learn more about algorithms in programming. You can also practice similar questions on Code studio.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think