Recuento de números perfectos en un rango dado para consultas Q

Dada una array arr[] que consta de N pares , donde cada par representa una consulta de la forma {L, R} , la tarea es encontrar el recuento de números perfectos en el rango dado para cada consulta.

Ejemplos:

Entrada: arr[][] = {{1, 10}, {10, 20}, {20, 30}}
Salida: 1 1 1
Explicación:

1. Consulta (1, 10): los números perfectos en el rango son solo 6.
2. Consulta (10, 20): No hay números perfectos en el rango.
3. Consulta (20, 30): el número perfecto en el rango es solo 28.

Entrada: arr[][] = {{1, 1000}, {1000, 2000}, {2000, 3000}
Salida: 3 0 0
Explicación:

1. Consulta (1, 1000): los números perfectos en el rango son 6, 28 y 496.
2. Consulta (1000, 2000): No hay números perfectos en el rango.
3. Consulta (2000, 3000): no hay números perfectos en el rango.

Enfoque ingenuo: el enfoque más simple es iterar sobre el rango en cada consulta y verificar si un número es un número perfecto o no , y luego imprimir el conteo de números perfectos en el rango para la consulta respectiva.

Complejidad de tiempo: O(N*M*√M)), donde M es el tamaño más grande de un rango. 
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar prealmacenando el recuento de números perfectos desde 1 hasta cualquier otro número utilizando la técnica de array de suma de prefijos , que da como resultado un cálculo de tiempo constante de cada consulta. Siga los pasos a continuación para resolver el problema:

• Encuentre el valor máximo del límite derecho de un rango recorriendo la array arr[] y guárdelo en una variable, digamos MAX.
• Inicialice una array, digamos prefijo[] de tamaño MAX+1 con el valor de cada elemento como 0 , donde el prefijo[i] almacena el recuento de números perfectos hasta i .
• Itere sobre el rango [2, MAX] usando la variable i y haga lo siguiente:
  • Actualice el prefijo [i] al prefijo [i-1] y luego verifique si el entero i actual es un número perfecto , luego aumente el prefijo [i] en 1.
• Recorra la array arr[] y en cada iteración imprima el conteo de números perfectos en el rango actual, [L, R] como prefijo[R] – prefijo[L-1].

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100005;
 
// Function to check whether a number
// is perfect Number
bool isPerfect(long long int N)
{
    // Stores sum of divisors
    long long int sum = 1;
 
    // Iterate over the range[2, sqrt(N)]
    for (long long 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 sum of divisors is equal to
    // N, then N is a perfect number
    if (sum == N && N != 1)
        return true;
 
    return false;
}
 
// Function to find count of perfect
// numbers in a given range
void Query(int arr[][2], int N)
{
    // Stores the count of perfect Numbers
    // upto a every number less than MAX
    int prefix[MAX + 1] = { 0 };
 
    // Iterate over the range [1, MAX]
    for (int i = 2; i <= MAX; i++) {
        prefix[i] = prefix[i - 1] + isPerfect(i);
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
        // Print the count of perfect numbers
        // in the range [arr[i][0], arr[i][1]]
        cout << prefix[arr[i][1]] - prefix[arr[i][0] - 1]
             << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[][2]
        = { { 1, 1000 }, { 1000, 2000 }, { 2000, 3000 } };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    Query(arr, N);
}

// C++ program for the above approach
import java.util.*;
public class MyClass
{
 
static int MAX = 100005;
 
// Function to check whether a number
// is perfect Number
static int isPerfect(long N)
{
   
    // Stores sum of divisors
    long  sum = 1;
 
    // Iterate over the range[2, sqrt(N)]
    for (long i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            if (i * i != N)
                sum = sum + i + N / i;
            else
                sum = sum + i;
        }
    }
   
    // If sum of divisors is equal to
    // N, then N is a perfect number
    if (sum == N && N != 1)
        return 1;
 
    return 0;
}
 
// Function to find count of perfect
// numbers in a given range
static void Query(int arr[][], int N)
{
   
    // Stores the count of perfect Numbers
    // upto a every number less than MAX
    int []prefix = new int [MAX + 1];
    Arrays.fill(prefix,0);
 
    // Iterate over the range [1, MAX]
    for (int i = 2; i <= MAX; i++) {
        prefix[i] = prefix[i - 1] + isPerfect(i);
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++)
    {
       
        // Print the count of perfect numbers
        // in the range [arr[i][0], arr[i][1]]
       System.out.print( prefix[arr[i][1]] - prefix[arr[i][0] - 1]+ " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    int [][]arr = { { 1, 1000 }, { 1000, 2000 }, { 2000, 3000 } };
    int N = arr.length;
 
    Query(arr, N);
}
}
 
// This code is contributed by SoumikMondal

# python 3 program for the above approach
MAX = 100005
 
from math import sqrt
 
# Function to check whether a number
# is perfect Number
def isPerfect(N):
   
    # Stores sum of divisors
    sum = 1
 
    # Iterate over the range[2, sqrt(N)]
    for i in range(2,int(sqrt(N))+1,1):
        if (N % i == 0):
            if (i * i != N):
                sum = sum + i + N // i
            else:
                sum = sum + i
 
    # If sum of divisors is equal to
    # N, then N is a perfect number
    if (sum == N and N != 1):
        return True
 
    return False
 
# Function to find count of perfect
# numbers in a given range
def Query(arr, N):
   
    # Stores the count of perfect Numbers
    # upto a every number less than MAX
    prefix = [0 for i in range(MAX + 1)]
 
    # Iterate over the range [1, MAX]
    for i in range(2,MAX+1,1):
        prefix[i] = prefix[i - 1] + isPerfect(i)
 
    # Traverse the array arr[]
    for i in range(N):
       
        # Print the count of perfect numbers
        # in the range [arr[i][0], arr[i][1]]
        print(prefix[arr[i][1]] - prefix[arr[i][0] - 1],end= " ")
 
# Driver Code
if __name__ == '__main__':
    arr = [[1, 1000],[1000, 2000],[2000, 3000]]
    N = len(arr)
    Query(arr, N)
     
    # This code is contributed by SURENDRA_GANGWAR.

// C# program for the above approach
using System;
public class MyClass {
 
    static int MAX = 100005;
 
    // Function to check whether a number
    // is perfect Number
    static int isPerfect(long N)
    {
 
        // Stores sum of divisors
        long sum = 1;
 
        // Iterate over the range[2, sqrt(N)]
        for (long i = 2; i * i <= N; i++) {
            if (N % i == 0) {
                if (i * i != N)
                    sum = sum + i + N / i;
                else
                    sum = sum + i;
            }
        }
 
        // If sum of divisors is equal to
        // N, then N is a perfect number
        if (sum == N && N != 1)
            return 1;
 
        return 0;
    }
 
    // Function to find count of perfect
    // numbers in a given range
    static void Query(int[, ] arr, int N)
    {
 
        // Stores the count of perfect Numbers
        // upto a every number less than MAX
        int[] prefix = new int[MAX + 1];
        // Arrays.fill(prefix,0);
 
        // Iterate over the range [1, MAX]
        for (int i = 2; i <= MAX; i++) {
            prefix[i] = prefix[i - 1] + isPerfect(i);
        }
 
        // Traverse the array arr[]
        for (int i = 0; i < N; i++) {
 
            // Print the count of perfect numbers
            // in the range [arr[i][0], arr[i][1]]
            Console.Write(prefix[arr[i, 1]]
                          - prefix[arr[i, 0] - 1] + " ");
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int[, ] arr = { { 1, 1000 },
                        { 1000, 2000 },
                        { 2000, 3000 } };
        int N = arr.GetLength(0);
 
        Query(arr, N);
    }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript program for the above approach
 
 
        const MAX = 100005;
 
        // Function to check whether a number
        // is perfect Number
        function isPerfect(N) {
            // Stores sum of divisors
            let sum = 1;
 
            // Iterate over the range[2, sqrt(N)]
            for (let i = 2; i * i <= N; i++) {
                if (N % i == 0) {
                    if (i * i != N)
                        sum = sum + i + Math.floor(N / i);
                    else
                        sum = sum + i;
                }
            }
            // If sum of divisors is equal to
            // N, then N is a perfect number
            if (sum == N && N != 1)
                return true;
 
            return false;
        }
 
        // Function to find count of perfect
        // numbers in a given range
        function Query(arr, N) {
            // Stores the count of perfect Numbers
            // upto a every number less than MAX
            let prefix = new Array(MAX + 1).fill(0);
 
            // Iterate over the range [1, MAX]
            for (let i = 2; i <= MAX; i++) {
                prefix[i] = prefix[i - 1] + isPerfect(i);
            }
 
            // Traverse the array arr[]
            for (let i = 0; i < N; i++) {
                // Print the count of perfect numbers
                // in the range [arr[i][0], arr[i][1]]
                document.write(prefix[arr[i][1]] - prefix[arr[i][0] - 1] + " ");
            }
        }
 
        // Driver Code
 
        let arr
            = [[1, 1000], [1000, 2000], [2000, 3000]];
        let N = arr.length;
 
        Query(arr, N);
 
    // This code is contributed by Potta Lokesh
 
    </script>

3 0 0 

Complejidad de tiempo: O(M*√M+ N), donde M es el límite derecho más grande.
Espacio Auxiliar: O(M)