Tutorialspoint.dev

Sum of all divisors from 1 to n

Given a positive integer n. Find the value of sum_{i=1}^{i=n} F(i) 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 <bits/stdc++.h>
  
// 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.*/

PHP

<?php
// PHP program to find sum of all
// divisor of number up to 'n'
  
// Utility function to find sum of
// all divisor of number up to 'n'
  
function divisorSum($n
{
    $sum = 0;
  
    for ($i = 1; $i <= $n; ++$i
    {
  
        // Find all divisors of i
        // and add them 
        for ($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
$n = 4;
echo " ", divisorSum($n), " ";
$n = 5;
echo divisorSum($n), " ";
  
// This code is contributed by aj_36
?>


Output :

15
21

Time complexity: O(nsqrt{n} )
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 <stdio.h>
  
// 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

<?php
// PHP program to find sum of all
// divisor of number up to 'n'
  
// Utility function to find sum of
// all divisor of number up to 'n'
function divisorSum( $n)
{
    $sum = 0;
    for ( $i = 1; $i <= $n; ++$i)
        $sum += floor($n / $i) * $i;
    return $sum;
}
  
// Driver code
$n = 4;
echo divisorSum($n)," ";
$n = 5;
echo divisorSum($n)," ";
  
// This code is contributed by anuj_67.
?>


Output :

15
21

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter