Suma de piso de progresión armónica

Dado un número entero N , la tarea es encontrar la suma de la serie armónica  .
Ejemplos: 
 

Entrada: N = 5 
Salida: 10 
piso (3/1) + piso (3/2) + piso (3/3) = 3 + 1 + 1 = 5
Entrada: N = 20 
Salida: 66 
 

Enfoque ingenuo: ejecute un ciclo de 1 a N y encuentre la suma de los valores mínimos de N / i . La complejidad temporal de este enfoque será O(n) .
Enfoque eficiente: use la siguiente fórmula para calcular la suma de la serie: 

ahora, el ciclo debe ejecutarse de 1 a sqrt (N) y la complejidad del tiempo se reduce a O (sqrt (N))
A continuación se muestra la implementación de la enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the summation of
// the given harmonic series
long long int getSum(int n)
{
 
    // To store the summation
    long long int sum = 0;
 
    // Floor of sqrt(n)
    int k = sqrt(n);
 
    // Summation of floor(n / i)
    for (int i = 1; i <= k; i++) {
        sum += floor(n / i);
    }
 
    // From the formula
    sum *= 2;
    sum -= pow(k, 2);
 
    return sum;
}
 
// Driver code
int main()
{
    int n = 5;
 
    cout << getSum(n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
    // Function to return the summation of
    // the given harmonic series
    static long getSum(int n)
    {
     
        // To store the summation
        long sum = 0;
     
        // Floor of sqrt(n)
        int k = (int)Math.sqrt(n);
     
        // Summation of floor(n / i)
        for (int i = 1; i <= k; i++)
        {
            sum += Math.floor(n / i);
        }
     
        // From the formula
        sum *= 2;
        sum -= Math.pow(k, 2);
     
        return sum;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 5;
     
        System.out.println(getSum(n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
from math import floor, sqrt, ceil
 
# Function to return the summation of
# the given harmonic series
def getSum(n):
 
    # To store the summation
    summ = 0
 
    # Floor of sqrt(n)
    k =(n)**(.5)
 
    # Summation of floor(n / i)
    for i in range(1, floor(k) + 1):
        summ += floor(n / i)
 
    # From the formula
    summ *= 2
    summ -= pow(floor(k), 2)
 
    return summ
 
# Driver code
n = 5
 
print(getSum(n))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
     
class GFG
{
     
    // Function to return the summation of
    // the given harmonic series
    static double getSum(int n)
    {
     
        // To store the summation
        double sum = 0;
     
        // Floor of sqrt(n)
        int k = (int)Math.Sqrt(n);
     
        // Summation of floor(n / i)
        for (int i = 1; i <= k; i++)
        {
            sum += Math.Floor((double)n / i);
        }
     
        // From the formula
        sum *= 2;
        sum -= Math.Pow(k, 2);
     
        return sum;
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int n = 5;
     
        Console.WriteLine(getSum(n));
    }
}
     
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation of the approach
 
// Function to return the summation of
// the given harmonic series
function getSum(n)
{
 
    // To store the summation
    let sum = 0;
 
    // Floor of sqrt(n)
    let k = parseInt(Math.sqrt(n));
 
    // Summation of floor(n / i)
    for (let i = 1; i <= k; i++) {
        sum += Math.floor(n / i);
    }
 
    // From the formula
    sum *= 2;
    sum -= Math.pow(k, 2);
 
    return sum;
}
 
// Driver code
    let n = 5;
 
    document.write(getSum(n));
 
</script>

10

Complejidad de tiempo: O(sqrt(n))

Espacio Auxiliar: O(1)