Suma del producto de todos los números enteros hasta N con su cuenta de divisores

Dado un entero positivo N , la tarea es encontrar la suma del producto de todos los enteros en el rango [1, N] con su cuenta de divisores . 

Ejemplos:

Entrada: N = 3
Salida: 11
Explicación:
El número de divisores positivos de 1 es 1 (es decir, 1 mismo). Por lo tanto, f(1) = 1.
El número de divisores positivos de 2 es 2 (es decir, 1, 2). Por lo tanto, f(2) = 2.
El número de divisores positivos de 3 es 2 (es decir, 1, 3). Por lo tanto, f(3) = 2.
Entonces la respuesta es 1*f(1) + 2*f(2) + 3*f(3) = 1*1 + 2*2 + 3*2 = 11.

Entrada: N = 4
Salida: 23
Explicación:
Aquí f(1) = 1, f(2) = 2, f(3) = 2 y f(4) = 3. Entonces, la respuesta es 1*1 + 2* 2 + 3*2 + 4*3 = 23.

Enfoque ingenuo: El enfoque ingenuo es atravesar de 1 a N y encontrar la suma de todos los números con su cuenta de divisores .

Complejidad de tiempo: O(N*sqrt(N))
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es considerar la contribución total que cada número hace a la respuesta. A continuación se muestran los pasos: 

1. Para cualquier número X en el rango [1, N] , X aporta K a la suma de cada K de 1 a N tal que K es un múltiplo de X .
2. Obsérvese que la lista de estos K es de forma i, 2i, 3i, …, Fi donde F es el número de múltiplos de i entre 1 y N .
3. Por lo tanto, para encontrar la suma de estos números generados arriba está dado por 
    

i*(1+2+3 + … F) = i*(F*(F+1))/2. 
 

A continuación se muestra la implementación del enfoque anterior:

// 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 N
long 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 code
int main()
{
    // Given N
    int N = 3;
 
    // function call
    cout << sumOfFactors(N);
}

// Java program for the above approach
class GFG{
   
// Function to find the sum of the
// product of all the integers and
// their positive divisors up to N
static 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 code
public 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 implementation of
# the above approach
 
# Function to find the sum of the
# product of all the integers and
# their positive divisors up to N
def 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 N
N = 3
 
# Function call
print(sumOfFactors(N))
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
class GFG{
   
// Function to find the sum of the
// product of all the integers and
// their positive divisors up to N
static 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 code
public static void Main(String[] args)
{
    // Given N
    int N = 3;
  
    // function call
    Console.WriteLine(sumOfFactors(N));
}
}
 
// This code is contributed by gauravrajput1

<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>

11

Complejidad temporal: O(N)
Espacio auxiliar: O(1)