Sum of series (n/1) + (n/2) + (n/3) + (n/4) +…….+ (n/n)
Given a value n, find the sum of series, (n/1) + (n/2) + (n/3) + (n/4) +…….+(n/n) where the value of n can be up to 10^12.
Note: Consider only integer division.
Examples:
Input : n = 5 Output : (5/1) + (5/2) + (5/3) + (5/4) + (5/5) = 5 + 2 + 1 + 1 + 1 = 10 Input : 7 Output : (7/1) + (7/2) + (7/3) + (7/4) + (7/5) + (7/6) + (7/7) = 7 + 3 + 2 + 1 + 1 + 1 + 1 = 16
Below is the program to find the sum of given series:
C++
// CPP program to find // sum of given series #include <bits/stdc++.h> using namespace std; // function to find sum of series long long int sum( long long int n) { long long int root = sqrt (n); long long int ans = 0; for ( int i = 1; i <= root; i++) ans += n / i; ans = 2 * ans - (root * root); return ans; } // driver code int main() { long long int n = 35; cout << sum(n); return 0; } |
Java
// Java program to find // sum of given series import java.util.*; class GFG { // function to find sum of series static long sum( long n) { long root = ( long )Math.sqrt(n); long ans = 0 ; for ( int i = 1 ; i <= root; i++) ans += n / i; ans = 2 * ans - (root * root); return ans; } /* Driver code */ public static void main(String[] args) { long n = 35 ; System.out.println(sum(n)); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python 3 program to find # sum of given series import math # function to find sum of series def sum (n) : root = ( int )(math.sqrt(n)) ans = 0 for i in range ( 1 , root + 1 ) : ans = ans + n / / i ans = 2 * ans - (root * root) return ans # driver code n = 35 print ( sum (n)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find // sum of given series using System; class GFG { // Function to find sum of series static long sum( long n) { long root = ( long )Math.Sqrt(n); long ans = 0; for ( int i = 1; i <= root; i++) ans += n / i; ans = 2 * ans - (root * root); return ans; } // Driver code public static void Main() { long n = 35; Console.Write(sum(n)); } } // This code is contributed vt_m. |
PHP
<?php // PHP program to find // sum of given series // function to find // sum of series function sum( $n ) { $root = intval (sqrt( $n )); $ans = 0; for ( $i = 1; $i <= $root ; $i ++) $ans += intval ( $n / $i ); $ans = (2 * $ans ) - ( $root * $root ); return $ans ; } // Driver code $n = 35; echo (sum( $n )); // This code is contributed by // Manish Shaw(manishshaw1) ?> |
Javascript
<script> // Javascript program to find // sum of given series // function to find // sum of series function sum(n) { let root = parseInt(Math.sqrt(n)); let ans = 0; for (let i = 1; i <= root; i++) ans += parseInt(n / i); ans = (2 * ans) - (root * root); return ans; } // Driver code let n = 35; document.write(sum(n)); // This code is contributed by gfgking. </script> |
Output:
131
Time complexity: O(sqrt(n)) as for loop will run by sqrt(n) times
Auxiliary Space: O(1)
Note: If observed closely, we can see that, if we take n common, series turns into an Harmonic Progression.
Contact Us