# Sum of all divisors from 1 to n

Given a positive integer n. Find the value of where function F(i) for number i be defined as sum of all divisors of ‘i‘.
Examples :

```Input: 4
Output: 15
Explanation
F(1) = 1
F(2) = 1 + 2 = 3
F(3) = 1 + 3 = 4
F(4) = 1 + 2 + 4 = 7
ans = F(1) + F(2) + F(3) + F(4)
= 1 + 3 + 4 + 7
= 15

Input: 5
Output: 21
```

Naive approach is to traverse for every number(1 to n), find all divisors and keep updating the sum with that divisor. See this to understand more.

## C++

 `// CPP program to find sum of all ` `// divisor of number up to 'n' ` `#include ` ` `  `// Utility function to find sum of ` `// all divisor of number up to 'n' ` `int` `divisorSum(``int` `n) i ` `{ ` `    ``int` `sum = 0; ` ` `  `    ``for` `(``int` `i = 1; i <= n; ++i) { ` ` `  `        ``// Find all divisors of i and add them ` `        ``for` `(``int` `j = 1; j * j <= i; ++j) { ` `            ``if` `(i % j == 0) { ` `                ``if` `(i / j == j) ` `                    ``sum += j; ` `                ``else` `                    ``sum += j + i / j; ` `            ``} ` `        ``} ` `    ``} ` `    ``return` `sum; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 4; ` `    ``printf``(````"%d "````, divisorSum(n)); ` `    ``n = 5; ` `    ``printf``(``"%d"``, divisorSum(n)); ` `    ``return` `0; ` `} `

## Java

 `// JAVA program to find sum of all ` `// divisor of number up to 'n' ` `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``// Utility function to find sum of ` `    ``// all divisor of number up to 'n' ` `    ``static` `int` `divisorSum(``int` `n) ` `    ``{ ` `        ``int` `sum = ``0``; ` ` `  `        ``for` `(``int` `i = ``1``; i <= n; ++i) { ` ` `  `            ``// Find all divisors of i ` `            ``// and add them ` `            ``for` `(``int` `j = ``1``; j * j <= i; ++j) { ` `                ``if` `(i % j == ``0``) { ` `                    ``if` `(i / j == j) ` `                        ``sum += j; ` `                    ``else` `                        ``sum += j + i / j; ` `                ``} ` `            ``} ` `        ``} ` `        ``return` `sum; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``4``; ` `        ``System.out.println(divisorSum(n)); ` `        ``n = ``5``; ` `        ``System.out.println(divisorSum(n)); ` `    ``} ` `} ` ` `  `/*This code is contributed by Nikita tiwari.*/`

## Python3

 `# Python3 code to find sum of all ` `# divisor of number up to 'n' ` ` `  `# Utility function to find sum of ` `# all divisor of number up to 'n' ` `def` `divisorSum( n ): ` `    ``sum` `=` `0` `     `  `    ``for` `i ``in` `range``(``1``, n ``+` `1``): ` `         `  `        ``# Find all divisors of i ` `        ``# and add them ` `        ``j ``=` `1` `        ``while` `j ``*` `j <``=` `i: ` `            ``if` `i ``%` `j ``=``=` `0``: ` `                ``if` `i ``/` `j ``=``=` `j: ` `                    ``sum` `+``=` `j ` `                ``else``: ` `                    ``sum` `+``=` `j ``+` `i ``/` `j ` `            ``j ``=` `j ``+` `1` `    ``return` `int``(``sum``) ` ` `  `# Driver code ` `n ``=` `4` `print``( divisorSum(n)) ` `n ``=` `5` `print``( divisorSum(n)) ` ` `  `# This code is contributed by "Sharad_Bhardwaj". `

## C#

 `// C# program to find sum of all ` `// divisor of number up to 'n' ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Utility function to find sum of ` `    ``// all divisor of number up to 'n' ` `    ``static` `int` `divisorSum(``int` `n) ` `    ``{ ` `        ``int` `sum = 0; ` ` `  `        ``for` `(``int` `i = 1; i <= n; ++i) { ` ` `  `            ``// Find all divisors of i ` `            ``// and add them ` `            ``for` `(``int` `j = 1; j * j <= i; ++j) { ` `                ``if` `(i % j == 0) { ` `                    ``if` `(i / j == j) ` `                        ``sum += j; ` `                    ``else` `                        ``sum += j + i / j; ` `                ``} ` `            ``} ` `        ``} ` `        ``return` `sum; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 4; ` `        ``Console.WriteLine(divisorSum(n)); ` `        ``n = 5; ` `        ``Console.WriteLine(divisorSum(n)); ` `    ``} ` `} ` ` `  `/*This code is contributed by vt_m.*/`

/div>

## PHP

 ` `

Output :

```15
21
```

Time complexity: O()
Auxiliary space: O(1)

Efficient approach is to observe the function and co-relate the pattern. For a given number n, every number from 1 to n contribute it’s presence up to the highest multiple less than n. For instance,

```Let n = 6,
=> F(1) + F(2) + F(3) + F(4) + F(5) + F(6)
=> 1 will occurs 6 times in F(1), F(2),
F(3), F(4), F(5) and F(6)
=> 2 will occurs 3 times in F(2), F(4) and
F(6)
=> 3 will occur 2 times in F(3) and F(6)
=> 4 will occur 1 times in F(4)
=> 5 will occur 1 times in F(5)
=> 6 will occur 1 times in F(6)
```

From above observation, it can easily be observed that number i is occurring only in there multiples less than or equal to n. Thus, we just need to find the count of multiples and then multiply it with i for full contribution in the final sum. It can easily be done in O(1) time by taking floor of (n / i) and then multiply it with i for the sum.

## C++

 `// CPP program to find sum of all ` `// divisor of number up to 'n' ` `#include ` ` `  `// Utility function to find sum of ` `// all divisor of number up to 'n' ` `int` `divisorSum(``int` `n) ` `{ ` `    ``int` `sum = 0; ` `    ``for` `(``int` `i = 1; i <= n; ++i) ` `        ``sum += (n / i) * i; ` `    ``return` `sum; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 4; ` `    ``printf``(````"%d "````, divisorSum(n)); ` `    ``n = 5; ` `    ``printf``(``"%d"``, divisorSum(n)); ` `    ``return` `0; ` `} `

## Java

 `// Java program to find sum of all ` `// divisor of number up to 'n' ` `import` `java.io.*; ` ` `  `class` `GFG { ` ` `  `    ``// Utility function to find sum of ` `    ``// all divisor of number up to 'n' ` `    ``static` `int` `divisorSum(``int` `n) ` `    ``{ ` `        ``int` `sum = ``0``; ` `        ``for` `(``int` `i = ``1``; i <= n; ++i) ` `            ``sum += (n / i) * i; ` `        ``return` `sum; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``4``; ` `        ``System.out.println(divisorSum(n)); ` `        ``n = ``5``; ` `        ``System.out.println(divisorSum(n)); ` `    ``} ` `} ` ` `  `/*This code is contributed by Nikita Tiwari.*/`

## Python3

 `# Python3 code to find sum of all ` `# divisor of number up to 'n' ` ` `  `# Utility function to find sum of ` `# all divisor of number up to 'n' ` `def` `divisorSum( n ): ` `    ``sum` `=` `0` `    ``for` `i ``in` `range``(``1``, n ``+` `1``): ` `        ``sum` `+``=` `int``(n ``/` `i) ``*` `i ` `    ``return` `int``(``sum``) ` `     `  `# Driver code ` `n ``=` `4` `print``( divisorSum(n)) ` `n ``=` `5` `print``( divisorSum(n)) ` ` `  `# This code is contributed by "Sharad_Bhardwaj". `

## C#

 `// C# program to find sum of all ` `// divisor of number up to 'n' ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Utility function to find sum of ` `    ``// all divisor of number up to 'n' ` `    ``static` `int` `divisorSum(``int` `n) ` `    ``{ ` `        ``int` `sum = 0; ` `        ``for` `(``int` `i = 1; i <= n; ++i) ` `            ``sum += (n / i) * i; ` `        ``return` `sum; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 4; ` `        ``Console.WriteLine(divisorSum(n)); ` `        ``n = 5; ` `        ``Console.WriteLine(divisorSum(n)); ` `    ``} ` `} ` ` `  `/*This code is contributed by vt_m.*/`

## PHP

 ` `

Output :

```15
21
```

Time complexity: O(n)
Auxiliary space: O(1)