Suma de todos los números perfectos que se encuentran en el rango [L, R]

Posted on by Rudeus Greyrat

Dados dos números L , R que significan el rango [L, R] , la tarea es encontrar la suma de todos los números perfectos que se encuentran en el rango [L, R].
Ejemplos: 
 

Entrada: L = 6, R = 10 
Salida: 6 
Explicación: 
Del 6 al 10, el único número perfecto es 6.
Entrada: L = 6, R = 28 
Salida: 34 
Explicación: 
Hay dos números perfectos en el rango [6 , 28]. Son, {6, 28} 
6 + 28 = 34. 
 

Enfoque ingenuo: el enfoque ingenuo para este problema es verificar si un número es un número perfecto o no iterando a través de cada número en el rango [L, R]. Si hay N números en el rango, la complejidad de tiempo para este enfoque es O(N * sqrt(K)) donde K es el número máximo (R) en el rango [L, R].
Enfoque eficiente: la idea es utilizar el concepto de array de suma de prefijos para realizar cálculos previos y almacenar la suma de todos los números en una array. 
 

  • Inicialice una array hasta el tamaño máximo de modo que cada índice ‘i’ de la array represente la suma de todos los números perfectos de [0, i] .
  • Itere sobre la array y para cada índice, verifique si es un número perfecto o no.
  • Si es un número perfecto, sume la suma almacenada en el índice anterior (i – 1) y el índice actual ‘i’.
  • Si no es un número perfecto, sume la suma almacenada en el índice anterior (i – 1) y el valor 0.
  • Finalmente, para cada consulta [L, R], devuelva el valor: 
     
sum = arr[R] - arr[L - 1]

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

C++

// C++ implementation to find the
// sum of all perfect numbers
// lying in the range [L, R]
 
#include <bits/stdc++.h>
#define ll int
using namespace std;
 
// Array to store the sum
long long pref[100010];
 
// Function to check if a number is
// a perfect number or not
int isPerfect(int n)
{
    int sum = 1;
 
    // Iterating till the square root
    // of the number and checking if
    // the sum of divisors is equal
    // to the number or not
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            if (i * i != n)
                sum = sum + i + n / i;
            else
                sum = sum + i;
        }
    }
 
    // If it is a perfect number, then
    // return the number
    if (sum == n && n != 1)
        return n;
 
    // Else, return 0
    return 0;
}
 
// Function to precompute the sum
// of perfect squares and store
// then in an array
void precomputation()
{
    for (int i = 1; i <= 100000; ++i) {
        pref[i] = pref[i - 1] + isPerfect(i);
    }
}
 
int main()
{
 
    int L = 6, R = 28;
 
    precomputation();
 
    cout << pref[R] - pref[L - 1];
 
    return 0;
}

Java

// Java implementation to find the
// sum of all perfect numbers
// lying in the range [L, R]
class GFG {
     
    // Array to store the sum
    static int pref [] = new int[10000];
     
    // Function to check if a number is
    // a perfect number or not
    static int isPerfect(int n)
    {
        int sum = 1;
     
        // Iterating till the square root
        // of the number and checking if
        // the sum of divisors is equal
        // to the number or not
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                if (i * i != n)
                    sum = sum + i + n / i;
                else
                    sum = sum + i;
            }
        }
     
        // If it is a perfect number, then
        // return the number
        if (sum == n && n != 1)
            return n;
     
        // Else, return 0
        return 0;
    }
     
    // Function to precompute the sum
    // of perfect squares and store
    // then in an array
    static void precomputation()
    {
        for (int i = 1; i < 10000; ++i) {
            pref[i] = pref[i - 1] + isPerfect(i);
        }
    }
     
    public static void main (String[] args)
    {
     
        int L = 6, R = 28;
     
        precomputation();
     
        System.out.println(pref[R] - pref[L - 1]);
     
    }
 
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation to find the
# sum of all perfect numbers
# lying in the range [L, R]
 
from math import sqrt
 
# Array to store the sum
pref = [0]*10000;
 
# Function to check if a number is
# a perfect number or not
def isPerfect(n)  :
 
    sum = 1;
 
    # Iterating till the square root
    # of the number and checking if
    # the sum of divisors is equal
    # to the number or not
    for i in range(2, int(sqrt(n)) + 1) :
        if (n % i == 0) :
            if (i * i != n) :
                sum = sum + i + n // i;
            else :
                sum = sum + i;
                 
    # If it is a perfect number, then
    # return the number
    if (sum == n and n != 1) :
        return n;
 
    # Else, return 0
    return 0;
 
# Function to precompute the sum
# of perfect squares and store
# then in an array
def precomputation() :
 
    for i in range(1, 10000) :
        pref[i] = pref[i - 1] + isPerfect(i);
 
if __name__ == "__main__" :
 
 
    L = 6; R = 28;
 
    precomputation();
 
    print(pref[R] - pref[L - 1]);
 
# This code is contributed by AnkitRai01

C#

// C# implementation to find the
// sum of all perfect numbers
// lying in the range [L, R]
using System;
 
public class GFG {
      
    // Array to store the sum
    static int []pref = new int[10000];
      
    // Function to check if a number is
    // a perfect number or not
    static int isPerfect(int n)
    {
        int sum = 1;
      
        // Iterating till the square root
        // of the number and checking if
        // the sum of divisors is equal
        // to the number or not
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                if (i * i != n)
                    sum = sum + i + n / i;
                else
                    sum = sum + i;
            }
        }
      
        // If it is a perfect number, then
        // return the number
        if (sum == n && n != 1)
            return n;
      
        // Else, return 0
        return 0;
    }
      
    // Function to precompute the sum
    // of perfect squares and store
    // then in an array
    static void precomputation()
    {
        for (int i = 1; i < 10000; ++i) {
            pref[i] = pref[i - 1] + isPerfect(i);
        }
    }
      
    public static void Main(String[] args)
    {
      
        int L = 6, R = 28;
      
        precomputation();
      
        Console.WriteLine(pref[R] - pref[L - 1]);
      
    }
  
}
// This code contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation to find the
// sum of all perfect numbers
// lying in the range [L, R]
 
// Array to store the sum
var pref = Array(100010).fill(0);
 
// Function to check if a number is
// a perfect number or not
function isPerfect(n)
{
    var sum = 1;
 
    // Iterating till the square root
    // of the number and checking if
    // the sum of divisors is equal
    // to the number or not
    for (var i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            if (i * i != n)
                sum = sum + i + n / i;
            else
                sum = sum + i;
        }
    }
 
    // If it is a perfect number, then
    // return the number
    if (sum == n && n != 1)
        return n;
 
    // Else, return 0
    return 0;
}
 
// Function to precompute the sum
// of perfect squares and store
// then in an array
function precomputation()
{
    for (var i = 1; i <= 100000; ++i) {
        pref[i] = pref[i - 1] + isPerfect(i);
    }
}
 
var L = 6, R = 28;
precomputation();
document.write( pref[R] - pref[L - 1]);
 
// This code is contributed by noob2000.
</script>
Producción: 

34

 

Complejidad del tiempo: 
 

  • El tiempo necesario para el precálculo es O(K * sqrt(K)) donde K es el número hasta el cual estamos realizando el precálculo
  • Después del cálculo previo, cada consulta se responde en O(1) .

 Espacio Auxiliar: O(10 5 )

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *