# Sum of all the factors of a number

Given a number n, the task is to find the sum of all the divisors.

Examples :

```Input : n = 30
Output : 72
Dividers sum 1 + 2 + 3 + 5 + 6 +
10 + 15 + 30 = 72

Input :  n = 15
Output : 24
Dividers sum 1 + 3 + 5 + 15 = 24
```

A simple solution is to traverse through all divisors and add them.

## C++

 `// Simple C++ program to  ` `// find sum of all divisors  ` `// of a natural number ` `#include ` `using` `namespace` `std; ` `  `  `// Function to calculate sum of all  ` `//divisors of a given number ` `int` `divSum(``int` `n) ` `{ ` `    ``// Sum of divisors ` `    ``int` `result = 0; ` `  `  `    ``// find all divisors which divides 'num' ` `    ``for` `(``int` `i = 2; i <= ``sqrt``(n); i++) ` `    ``{ ` `        ``// if 'i' is divisor of 'n' ` `        ``if` `(n % i == 0) ` `        ``{ ` `            ``// if both divisors are same ` `            ``// then add it once else add ` `            ``// both ` `            ``if` `(i == (n / i)) ` `                ``result += i; ` `            ``else` `                ``result += (i + n/i); ` `        ``} ` `    ``} ` `  `  `    ``// Add 1 and n to result as above loop ` `    ``// considers proper divisors greater  ` `    ``// than 1. ` `    ``return` `(result + n + 1); ` `} ` `  `  `// Driver program to run the case ` `int` `main() ` `{ ` `    ``int` `n = 30; ` `    ``cout << divSum(n); ` `    ``return` `0; ` `} `

## Java

 `// Simple Java program to  ` `// find sum of all divisors  ` `// of a natural number ` `import` `java.io.*;  ` ` `  `class` `GFG { ` ` `  `    ``// Function to calculate sum of all  ` `    ``//divisors of a given number ` `    ``static` `int` `divSum(``int` `n) ` `    ``{ ` `        ``// Final result of summation  ` `        ``// of divisors ` `        ``int` `result = ``0``; ` `     `  `        ``// find all divisors which divides 'num' ` `        ``for` `(``int` `i = ``2``; i <= Math.sqrt(n); i++) ` `        ``{ ` `            ``// if 'i' is divisor of 'n' ` `            ``if` `(n % i == ``0``) ` `            ``{ ` `                ``// if both divisors are same ` `                ``// then add it once else add ` `                ``// both ` `                ``if` `(i == (n / i)) ` `                    ``result += i; ` `                ``else` `                    ``result += (i + n / i); ` `            ``} ` `        ``} ` `     `  `        ``// Add 1 and n to result as above loop ` `        ``// considers proper divisors greater ` `        ``// than 1. ` `        ``return` `(result + n + ``1``); ` `         `  `    ``} ` `     `  `    ``// Driver program to run the case ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `n = ``30``; ` `        ``System.out.println(divSum(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Prerna Saini.  `

## Python3

 `# Simple Python 3 program to  ` `# find sum of all divisors of ` `# a natural number ` `import` `math   ` ` `  `# Function to calculate sum  ` `# of all divisors of given ` `#  natural number ` `def` `divSum(n) : ` `     `  `    ``# Final result of summation  ` `    ``# of divisors ` `    ``result ``=` `0` `   `  `    ``# find all divisors which ` `    ``# divides 'num' ` `    ``for` `i ``in` `range``(``2``,(``int``)(math.sqrt(n))``+``1``) : ` ` `  `        ``# if 'i' is divisor of 'n' ` `        ``if` `(n ``%` `i ``=``=` `0``) : ` ` `  `            ``# if both divisors are same  ` `            ``# then add it only once ` `            ``# else add both ` `            ``if` `(i ``=``=` `(n``/``i)) : ` `                ``result ``=` `result ``+` `i ` `            ``else` `: ` `                ``result ``=` `result ``+` `(i ``+` `n``/``/``i) ` `         `  `         `  `    ``# Add 1 and n to result as above  ` `    ``# loop considers proper divisors ` `    ``# greater than 1. ` `    ``return` `(result ``+` `n ``+` `1``) ` `   `  `# Driver program to run the case ` `n ``=` `30` `print``(divSum(n)) ` ` `  `# This code is contributed by Nikita Tiwari. `

## C#

 `// Simple C# program to  ` `// find sum of all divisors  ` `// of a natural number ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Function to calculate sum of all  ` `    ``//divisors of a given number ` `    ``static` `int` `divSum(``int` `n) ` `    ``{ ` `        ``// Final result of summation  ` `        ``// of divisors ` `        ``int` `result = 0; ` `     `  `        ``// find all divisors which divides 'num' ` `        ``for` `(``int` `i = 2; i <= Math.Sqrt(n); i++) ` `        ``{ ` `            ``// if 'i' is divisor of 'n' ` `            ``if` `(n % i == 0) ` `            ``{ ` `                ``// if both divisors are same ` `                ``// then add it once else add ` `                ``// both ` `                ``if` `(i == (n / i)) ` `                    ``result += i; ` `                ``else` `                    ``result += (i + n / i); ` `            ``} ` `        ``} ` `     `  `        ``// Add 1 and n to result as above loop ` `        ``// considers proper divisors greater ` `        ``// than 1. ` `        ``return` `(result + n + 1); ` `    ``} ` `     `  `    ``// Driver program to run the case ` `    ``public` `static` `void` `Main() ` `    ``{ ` `         `  `        ``int` `n = 30; ` `         `  `        ``Console.WriteLine(divSum(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

 ` `

Output :

`72`

An efficient solution is to use below formula.
Let p1, p2, … pk be prime factors of n. Let a1, a2, .. ak be highest powers of p1, p2, .. pk respectively that divide n, i.e., we can write n as n = (p1a1)*(p2a2)* … (pkak).

```Sum of divisors = (1 + p1 + p12 ... p1a1) *
(1 + p2 + p22 ... p2a2) *
.............................................
(1 + pk + pk2 ... pkak)

We can notice that individual terms of above
formula are Geometric Progressions (GP). We
can rewrite the formula as.

Sum of divisors = (p1a1+1 - 1)/(p1 -1) *
(p2a2+1 - 1)/(p2 -1) *
..................................
(pkak+1 - 1)/(pk -1)
```

How does above formula work?

```Consider the number 18.

Sum of factors = 1 + 2 + 3 + 6 + 9 + 18

Writing divisors as powers of prime factors.
Sum of factors = (20)(30) + (21)(30) + (2^0)(31) +
(21)(31) + (20)(3^2) + (2^1)(32)
= (20)(30) + (2^0)(31) + (2^0)(32) +
(21)(3^0) + (21)(31) + (21)(32)
= (20)(30 + 31 + 32) +
(21)(30 + 31 + 32)
= (20 + 21)(30 + 31 + 32)
If we take a closer look, we can notice that the
above expression is in the form.
(1 + p1) * (1 + p2 + p22)
Where p1 = 2 and p2 = 3 and 18 = 2132```

So the task reduces to finding all prime factors and their powers.

## C++

 `// Formula based CPP program to ` `// find sum of all  divisors of n. ` `#include ` `using` `namespace` `std; ` ` `  `// Returns sum of all factors of n. ` `int` `sumofFactors(``int` `n) ` `{ ` `    ``// Traversing through all prime factors. ` `    ``int` `res = 1; ` `    ``for` `(``int` `i = 2; i <= ``sqrt``(n); i++) ` `    ``{ ` ` `  `         `  `        ``int` `curr_sum = 1; ` `        ``int` `curr_term = 1; ` `        ``while` `(n % i == 0) { ` ` `  `            ``// THE BELOW STATEMENT MAKES ` `            ``// IT BETTER THAN ABOVE METHOD  ` `            ``//  AS WE REDUCE VALUE OF n. ` `            ``n = n / i; ` ` `  `            ``curr_term *= i; ` `            ``curr_sum += curr_term; ` `        ``} ` ` `  `        ``res *= curr_sum; ` `    ``} ` ` `  `    ``// This condition is to handle  ` `    ``// the case when n is a prime ` `    ``// number greater than 2. ` `    ``if` `(n >= 2) ` `        ``res *= (1 + n); ` ` `  `    ``return` `res; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 30; ` `    ``cout << sumofFactors(n); ` `    ``return` `0; ` `} `

## Java

 `// Formula based Java program to  ` `// find sum of all divisors of n. ` ` `  `import` `java.io.*; ` `import` `java.math.*; ` `public` `class` `GFG{ ` `     `  `    ``// Returns sum of all factors of n. ` `    ``static` `int` `sumofFactors(``int` `n) ` `    ``{ ` `        ``// Traversing through all prime factors. ` `        ``int` `res = ``1``; ` `        ``for` `(``int` `i = ``2``; i <= Math.sqrt(n); i++) ` `        ``{ ` `     `  `             `  `            ``int`  `curr_sum = ``1``; ` `            ``int` `curr_term = ``1``; ` `             `  `            ``while` `(n % i == ``0``)  ` `            ``{ ` `     `  `                ``// THE BELOW STATEMENT MAKES ` `                ``// IT BETTER THAN ABOVE METHOD  ` `                ``// AS WE REDUCE VALUE OF n. ` `                ``n = n / i; ` `     `  `                ``curr_term *= i; ` `                ``curr_sum += curr_term; ` `            ``} ` `     `  `            ``res *= curr_sum; ` `        ``} ` `     `  `        ``// This condition is to handle  ` `        ``// the case when n is a prime  ` `        ``// number greater than 2 ` `        ``if` `(n > ``2``) ` `            ``res *= (``1` `+ n); ` `     `  `        ``return` `res; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``30``; ` `        ``System.out.println(sumofFactors(n)); ` `    ``} ` `} ` ` `  `/*This code is contributed by Nikita Tiwari.*/`

## Python3

 `# Formula based Python3 code to find  ` `# sum of all divisors of n. ` `import` `math as m ` ` `  `# Returns sum of all factors of n. ` `def` `sumofFactors(n): ` `     `  `    ``# Traversing through all ` `    ``# prime factors ` `    ``res ``=` `1` `    ``for` `i ``in` `range``(``2``, ``int``(m.sqrt(n) ``+` `1``)): ` `         `  `        ``curr_sum ``=` `1` `        ``curr_term ``=` `1` `         `  `        ``while` `n ``%` `i ``=``=` `0``: ` `             `  `            ``n ``=` `n ``/` `i; ` ` `  `            ``curr_term ``=` `curr_term ``*` `i; ` `            ``curr_sum ``+``=` `curr_term; ` `             `  `        ``res ``=` `res ``*` `curr_sum ` `     `  `    ``# This condition is to handle the  ` `    ``# case when n is a prime number  ` `    ``# greater than 2 ` `    ``if` `n > ``2``: ` `        ``res ``=` `res ``*` `(``1` `+` `n) ` ` `  `    ``return` `res; ` ` `  `# driver code     ` `sum` `=` `sumofFactors(``30``) ` `print` `(``"Sum of all divisors is: "``,``sum``) ` ` `  `# This code is contributed by Saloni Gupta `

## C#

 `// Formula based Java program to  ` `// find sum of all divisors of n. ` `using` `System; ` ` `  `public` `class` `GFG { ` `     `  `    ``// Returns sum of all factors of n. ` `    ``static` `int` `sumofFactors(``int` `n) ` `    ``{ ` `         `  `        ``// Traversing through all prime factors. ` `        ``int` `res = 1; ` `        ``for` `(``int` `i = 2; i <= Math.Sqrt(n); i++) ` `        ``{ ` `     `  `             `  `            ``int` `curr_sum = 1; ` `            ``int` `curr_term = 1; ` `             `  `            ``while` `(n % i == 0)  ` `            ``{ ` `     `  `                ``// THE BELOW STATEMENT MAKES ` `                ``// IT BETTER THAN ABOVE METHOD  ` `                ``// AS WE REDUCE VALUE OF n. ` `                ``n = n / i; ` `     `  `                ``curr_term *= i; ` `                ``curr_sum += curr_term; ` `            ``} ` `     `  `            ``res *= curr_sum; ` `        ``} ` `     `  `        ``// This condition is to handle  ` `        ``// the case when n is a prime  ` `        ``// number greater than 2 ` `        ``if` `(n > 2) ` `            ``res *= (1 + n); ` `     `  `        ``return` `res; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `         `  `        ``int` `n = 30; ` `         `  `        ``Console.WriteLine(sumofFactors(n)); ` `    ``} ` `} ` ` `  `/*This code is contributed by vt_m.*/`

## PHP

 ` 2) ` `        ``\$res` `*= (1 + ``\$n``); ` ` `  `    ``return` `\$res``; ` `} ` ` `  `// Driver Code ` `\$n` `= 30; ` `echo` `sumofFactors(``\$n``); ` ` `  `// This code is contributed by Anuj_67. ` `?> `

Output :

`72`

Further Optimization.
If there are multiple queries, we can use Sieve to find prime factors and their powers.