Given a positive integer N, the task is to find the sum of the product of all the integers in the range [1, N] with their count of divisors.
Examples:
Input: N = 3
Output: 11
Explanation:
Number of positive divisors of 1 is 1( i.e. 1 itself). Therefore, f(1) = 1.
Number of positive divisors of 2 is 2( i.e. 1, 2). Therefore, f(2) = 2.
Number of positive divisors of 3 is 2( i.e. 1, 3). Therefore, f(3) = 2.
So the answer is 1*f(1) + 2*f(2) + 3*f(3) = 1*1 + 2*2 + 3*2 = 11.Input: N = 4
Output: 23
Explanation:
Here f(1) = 1, f(2) = 2, f(3) = 2 and f(4) = 3. So, the answer is 1*1 + 2*2 + 3*2 + 4*3 = 23.
Naive Approach: The naive approach is to traverse from 1 to N and find the sum of all the numbers with their count of divisors.
Step by step algorithm:
- Initialize a variable ‘ans’ to 0.
- Traverse through every number ‘i’ between 1 and N.
- For each ‘i’, find the first multiple of ‘i’ between 1 and N, and store it in ‘first’.
- Find the last multiple of ‘i’ between 1 and N, and store it in ‘last’.
- Find the total count of multiples of ‘i’ in [1, N], and store it in ‘factors’ using the formula ((last – first) / i) + 1.
- Add ‘totalContribution’ to ‘ans’.
- Return ‘ans’ as the result.
C++
#include <iostream>#include <cmath>using namespace std;// Function to find sum of product of integers and their count of divisorslong long sumOfProduct(int N) { long long sum = 0; // Iterate from 1 to N for (int i = 1; i <= N; i++) { long long factors = 0; // Find the count of divisors of i by iterating from 1 to sqrt(i) for (int j = 1; j <= sqrt(i); j++) { if (i % j == 0) { factors++; // If the divisors are not the same, count them twice if (i / j != j) { factors++; } } } // Add the product of i and its count of divisors to the sum sum += (i * factors); } // Return the final sum return sum;}int main() { int N = 3; cout << sumOfProduct(N) << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to find sum of product of integers and their count of divisors public static long sumOfProduct(int N) { long sum = 0; // Iterate from 1 to N for (int i = 1; i <= N; i++) { long factors = 0; // Find the count of divisors of i by iterating from 1 to sqrt(i) for (int j = 1; j * j <= i; j++) { if (i % j == 0) { factors++; // If the divisors are not the same, count them twice if (i / j != j) { factors++; } } } // Add the product of i and its count of divisors to the sum sum += (i * factors); } // Return the final sum return sum; } public static void main(String[] args) { int N = 3; System.out.println(sumOfProduct(N)); }}//this code is contributed by utkarsh |
Python3
#Python program to implement above approachimport math# Function to find sum of product of integers and their count of divisorsdef sum_of_product(N): sum_result = 0 # Iterate from 1 to N for i in range(1, N+1): factors = 0 # Find the count of divisors of i by iterating from 1 to sqrt(i) for j in range(1, int(math.sqrt(i)) + 1): if i % j == 0: factors += 1 # If the divisors are not the same, count them twice if i // j != j: factors += 1 # Add the product of i and its count of divisors to the sum sum_result += i * factors # Return the final sum return sum_result#Driver Codedef main(): N = 3 print(sum_of_product(N))if __name__ == "__main__": main() |
C#
using System;class Program{ // Function to find sum of product of integers and their count of divisors static long SumOfProduct(int N) { long sum = 0; // Iterate from 1 to N for (int i = 1; i <= N; i++) { long factors = 0; // Find the count of divisors of i by iterating from 1 to sqrt(i) for (int j = 1; j * j <= i; j++) { if (i % j == 0) { factors++; // If the divisors are not the same, count them twice if (i / j != j) { factors++; } } } // Add the product of i and its count of divisors to the sum sum += (i * factors); } // Return the final sum return sum; } static void Main(string[] args) { int N = 3; Console.WriteLine(SumOfProduct(N)); }}/// this code is contributed by utkarsh |
Javascript
// Function to find sum of product of integers and their count of divisorsfunction sumOfProduct(N) { let sum = 0; // Iterate from 1 to N for (let i = 1; i <= N; i++) { let factors = 0; // Find the count of divisors of i by iterating from 1 to sqrt(i) for (let j = 1; j <= Math.sqrt(i); j++) { if (i % j === 0) { factors++; // If the divisors are not the same, count them twice if (i / j !== j) { factors++; } } } // Add the product of i and its count of divisors to the sum sum += (i * factors); } // Return the final sum return sum;}// Test with N = 3let N = 3;console.log(sumOfProduct(N));// This code is contributed by akshitaguprzj3 |
Output
11
Time Complexity: O(N*sqrt(N))
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to consider the total contribution each number makes to the answer. Below are the steps:
- For any number X in the range [1, N], X contributes K to the sum for each K from 1 to N such that K is a multiple of X.
- Observe that the list of these K is of form i, 2i, 3i, …, Fi where F is the number of multiples of i between 1 and N.
- Hence, to find the sum of these numbers generated above is given by
i*(1+2+3 + … F) = i*(F*(F+1))/2.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the sum of the// product of all the integers and// their positive divisors up to Nlong long sumOfFactors(int N){ long long ans = 0; // Iterate for every number // between 1 and N for (int i = 1; i <= N; i++) { // Find the first multiple // of i between 1 and N long long first = i; // Find the last multiple // of i between 1 and N long long last = (N / i) * i; // Find the total count of // multiple of in [1, N] long long factors = (last - first) / i + 1; // Compute the contribution of i // using the formula long long totalContribution = (((factors) * (factors + 1)) / 2) * i; // Add the contribution // of i to the answer ans += totalContribution; } // Return the result return ans;}// Driver codeint main(){ // Given N int N = 3; // function call cout << sumOfFactors(N);} |
Java
// Java program for the above approachclass GFG{ // Function to find the sum of the// product of all the integers and// their positive divisors up to Nstatic int sumOfFactors(int N){ int ans = 0; // Iterate for every number // between 1 and N for (int i = 1; i <= N; i++) { // Find the first multiple // of i between 1 and N int first = i; // Find the last multiple // of i between 1 and N int last = (N / i) * i; // Find the total count of // multiple of in [1, N] int factors = (last - first) / i + 1; // Compute the contribution of i // using the formula int totalContribution = (((factors) * (factors + 1)) / 2) * i; // Add the contribution // of i to the answer ans += totalContribution; } // Return the result return ans;} // Driver codepublic static void main(String[] args){ // Given N int N = 3; // function call System.out.println(sumOfFactors(N));}}// This code is contributed by Ritik Bansal |
Python3
# Python3 implementation of# the above approach# Function to find the sum of the# product of all the integers and# their positive divisors up to Ndef sumOfFactors(N): ans = 0 # Iterate for every number # between 1 and N for i in range(1, N + 1): # Find the first multiple # of i between 1 and N first = i # Find the last multiple # of i between 1 and N last = (N // i) * i # Find the total count of # multiple of in [1, N] factors = (last - first) // i + 1 # Compute the contribution of i # using the formula totalContribution = (((factors * (factors + 1)) // 2) * i) # Add the contribution # of i to the answer ans += totalContribution # Return the result return ans# Driver Code# Given NN = 3# Function call print(sumOfFactors(N))# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the sum of the// product of all the integers and// their positive divisors up to Nstatic int sumOfFactors(int N){ int ans = 0; // Iterate for every number // between 1 and N for (int i = 1; i <= N; i++) { // Find the first multiple // of i between 1 and N int first = i; // Find the last multiple // of i between 1 and N int last = (N / i) * i; // Find the total count of // multiple of in [1, N] int factors = (last - first) / i + 1; // Compute the contribution of i // using the formula int totalContribution = (((factors) * (factors + 1)) / 2) * i; // Add the contribution // of i to the answer ans += totalContribution; } // Return the result return ans;} // Driver codepublic static void Main(String[] args){ // Given N int N = 3; // function call Console.WriteLine(sumOfFactors(N));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// javascript program for the above approach // Function to find the sum of the // product of all the integers and // their positive divisors up to N function sumOfFactors(N) { var ans = 0; // Iterate for every number // between 1 and N for (i = 1; i <= N; i++) { // Find the first multiple // of i between 1 and N var first = i; // Find the last multiple // of i between 1 and N var last = parseInt(N / i) * i; // Find the total count of // multiple of in [1, N] var factors = parseInt((last - first) / i )+ 1; // Compute the contribution of i // using the formula var totalContribution = parseInt(((factors) * (factors + 1)) / 2) * i; // Add the contribution // of i to the answer ans += totalContribution; } // Return the result return ans; } // Driver code // Given N var N = 3; // function call document.write(sumOfFactors(N));// This code is contributed by todaysgaurav. </script> |
Output
11
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!
