Sum of all Perfect numbers lying in the range [L, R]

0 0 6 minutes read

Given two numbers L, R which signifies the range [L, R], the task is to find the sum of all perfect numbers lying in the range [L, R].
Examples:

Input: L = 6, R = 10
Output: 6
Explanation:
From 6 to 10, the only perfect number is 6.
Input: L = 6, R = 28
Output: 34
Explanation:
There are two perfect numbers in the range [6, 28]. They are, {6, 28}
6 + 28 = 34.

Naive Approach: The naive approach for this problem is to check if a number is a perfect number or not by iterating through every number in the range [L, R]. If there are N numbers in the range, the time complexity for this approach is O(N * sqrt(K)) where K is the maximum number(R) in the range [L, R].
Efficient Approach: The idea is to use the concept of prefix sum array to perform precomputations and store the sum of all the numbers in an array.

Initialize an array up to the max size such that every index ‘i’ of the array represents the sum of all the perfect numbers from [0, i].
Iterate over the array and for every index, check if it is a perfect number or not.
If it is a perfect number, then add the sum stored at the previous index (i – 1) and the current index ‘i’.
If it is not a perfect number, then add the sum stored at the previous index (i – 1) and the value 0.
Finally, for every query [L, R], return the value:

sum = arr[R] - arr[L - 1]

Below is the implementation of the above approach:

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>

Output:

Time Complexity:

The time taken for the precomputation is O(K * sqrt(K)) where K is the number upto which we are performing the precomputation
After precomputation, each query is answered in O(1).

Auxiliary Space: O(10⁵)

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