Given a positive integer N, the task is to find the sum of divisors of all the numbers from 1 to N.
Examples:
Input: N = 5
Output: 21
Explanation:
Sum of divisors of all numbers from 1 to 5 = 21.
Divisors of 1 -> 1
Divisors of 2 -> 1, 2
Divisors of 3 -> 1, 3
Divisors of 4 -> 1, 2, 4
Divisors of 5 -> 1, 5, hence Sum = 21Input: N = 6
Output: 33
Explanation:
Sum of divisors of all numbers from 1 to 6 = 33.
Divisors of 1 -> 1
Divisors of 2 -> 1, 2
Divisors of 3 -> 1, 3
Divisors of 4 -> 1, 2, 4
Divisors of 5 -> 1, 5
Divisors of 6 -> 1, 2, 3, 6, hence sum = 33
Naive and Linear Approach: Refer to the Sum of all divisors from 1 to n for the naive and linear approaches.
Logarithmic Approach: Refer to the Sum of all divisors from 1 to N | Set 2 for the logarithmic time approach.
Efficient Approach:
Follow the steps below to solve the problem:
- We can observe that for each number x from 1 to N, occurs in the sum up to it’s highest multiple which is ? N.
- Hence, calculate the contribution of each x by the formula x * floor(N / x),
- It can be observed that floor(N/i) is same for a series of continuous numbers l1, l2, l3….lr. Hence, instead of calculating li * floor(N/i) for each i, calculate (l1 + l2 + l3 +….+ lr) * floor(N/l1), thus reducing the computational complexity.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define int long long int#define m 1000000007// Function to find the sum// of all divisors of all// numbers from 1 to Nvoid solve(long long n){ // Stores the sum long long s = 0; for (int l = 1; l <= n;) { // Marks the last point of // occurrence with same count int r = n / floor(n / l); int x = (((r % m) * ((r + 1) % m)) / 2) % m; int y = (((l % m) * ((l - 1) % m)) / 2) % m; int p = ((n / l) % m); // Calculate the sum s = (s + (((x - y) % m) * p) % m + m) % m; s %= m; l = r + 1; } // Return the result cout << (s + m) % m;}// Driver Codesigned main(){ long long n = 12; solve(n); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{static final int m = 1000000007;// Function to find the sum// of all divisors of all// numbers from 1 to Nstatic void solve(long n){ // Stores the sum long s = 0; for (int l = 1; l <= n;) { // Marks the last point of // occurrence with same count int r = (int)(n / Math.floor(n / l)); int x = (((r % m) * ((r + 1) % m)) / 2) % m; int y = (((l % m) * ((l - 1) % m)) / 2) % m; int p = (int)((n / l) % m); // Calculate the sum s = (s + (((x - y) % m) * p) % m + m) % m; s %= m; l = r + 1; } // Return the result System.out.print((s + m) % m);}// Driver Codepublic static void main(String[] args){ long n = 12; solve(n);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 Program to implement# the above approachimport mathm = 1000000007# Function to find the sum# of all divisors of all# numbers from 1 to Ndef solve(n): # Stores the sum s = 0; l = 1; while(l < n + 1): # Marks the last point of # occurrence with same count r = (int)(n / math.floor(n / l)); x = ((((r % m) * ((r + 1) % m)) / 2) % m); y = ((((l % m) * ((l - 1) % m)) / 2) % m); p = (int)((n / l) % m); # Calculate the sum s = ((s + (((x - y) % m) * p) % m + m) % m); s %= m; l = r + 1; # Return the result print (int((s + m) % m));# Driver Codeif __name__ == '__main__': n = 12; solve(n);# This code is contributed by Rajput-Ji |
C#
// C# program to implement// the above approachusing System;class GFG{static readonly int m = 1000000007;// Function to find the sum// of all divisors of all// numbers from 1 to Nstatic void solve(long n){ // Stores the sum long s = 0; for(int l = 1; l <= n;) { // Marks the last point of // occurrence with same count int r = (int)(n /(Math.Floor((double)n/l))); int x = (((r % m) * ((r + 1) % m)) / 2) % m; int y = (((l % m) * ((l - 1) % m)) / 2) % m; int p = (int)((n / l) % m); // Calculate the sum s = (s + (((x - y) % m) * p) % m + m) % m; s %= m; l = r + 1; } // Return the result Console.Write((s + m) % m);}// Driver Codepublic static void Main(String[] args){ long n = 12; solve(n);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program implementation// of the approachlet m = 1000000007; // Function to find the sum// of all divisors of all// numbers from 1 to Nfunction solve(n){ // Stores the sum let s = 0; for (let l = 1; l <= n;) { // Marks the last point of // occurrence with same count let r = (n / Math.floor(n / l)); let x = Math.floor(((r % m) * ((r + 1) % m)) / 2) % m; let y = Math.floor(((l % m) * ((l - 1) % m)) / 2) % m; let p = (Math.floor(n / l) % m); // Calculate the sum s = (s + (((x - y) % m) * p) % m + m) % m; s %= m; l = r + 1; } // Return the result document.write((s + m) % m);} // Driver Code let n = 12; solve(n); // This code is contributed by splevel62.</script> |
Output
127
Time Complexity: O(?N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
