Encuentre la suma de todos los números prometidos hasta N

Dado un número N , la tarea es encontrar la suma de todos los números prometidos hasta N.

Sea A y B un par de números prometidos, entonces la suma de los divisores propios de A es igual a B+1 y la suma de los divisores propios de B es igual a A+1.

Ejemplos: 

Entrada: 78 
Salida: 123 
Explicación: 48 y 75 es el único par de números prometidos hasta el 78.

Entrada: 5 
Salida: 0 
Explicación: No hay ningún par de números de prometidos hasta el 50. 

Acercarse: 

• Inicialice la array para almacenar todos los números prometidos hasta N
• Encuentre los números prometidos usando la suma de todos sus divisores propios y almacene el par en la array.
• Luego encuentre la suma de todos los números menores que e iguales a N .
• La suma resultante es el valor requerido.

El siguiente código es la implementación del enfoque anterior: 

// C++ program to find the sum of the  
// all betrothed numbers up to N
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the sum of
// the all betrothed numbers
int Betrothed_Sum(int n)
{
    // To store the betrothed
    // numbers
    vector<int > Set;
     
    for(int number_1 = 1; number_1 < n;
                            number_1++)
    {
         
       // Calculate sum of
       // number_1's divisors
       // 1 is always a divisor
       int sum_divisor_1 = 1;
        
       // i = 2 because we don't
       // want to include
       // 1 as a divisor.
       int i = 2;
        
       while (i * i <= number_1)
       {
           if (number_1 % i == 0)
           {
               sum_divisor_1 = sum_divisor_1 + i;
                
               if (i * i != number_1)
                   sum_divisor_1 += number_1 / i;
           }
           i ++;
       }
       if (sum_divisor_1 > number_1)
       {
           int number_2 = sum_divisor_1 - 1;
           int sum_divisor_2 = 1;
           int j = 2;
            
           while (j * j <= number_2)
           {
               if (number_2 % j == 0)
               {
                   sum_divisor_2 += j;
                   if (j * j != number_2)
                       sum_divisor_2 += number_2 / j;
               }
               j = j + 1;
           }
           if (sum_divisor_2 == number_1 + 1 and
               number_1 <= n && number_2 <= n)
           {
               Set.push_back(number_1);
               Set.push_back(number_2);
           }
       }
    }
     
    // Sum all betrothed
    // numbers up to N
    int Summ = 0;
    for(auto i : Set)
    {
       if(i <= n)
          Summ += i;
    }
    return Summ;
}
 
// Driver code
int main()
{
    int n = 78;
     
    cout << Betrothed_Sum(n);
    return 0;
}
 
// This code is contributed by ishayadav181

// Java program to find the sum
// of the all betrothed numbers
// up to N 
import java.util.*;
 
class GFG{
     
// Function to find the sum of 
// the all betrothed numbers 
public static int Betrothed_Sum(int n)
{
     
    // To store the betrothed 
    // numbers 
    Vector<Integer> Set = new Vector<Integer>();
       
    for(int number_1 = 1;
            number_1 < n; 
            number_1++)
    {
         
       // Calculate sum of 
       // number_1's divisors 
       // 1 is always a divisor
       int sum_divisor_1 = 1;
          
       // i = 2 because we don't 
       // want to include 
       // 1 as a divisor. 
       int i = 2;
          
       while (i * i <= number_1)
       {
           if (number_1 % i == 0)
           {
               sum_divisor_1 = sum_divisor_1 + i;
                  
               if (i * i != number_1)
                   sum_divisor_1 += number_1 / i; 
           }
           i ++;
       }
        
       if (sum_divisor_1 > number_1)
       {
           int number_2 = sum_divisor_1 - 1;
           int sum_divisor_2 = 1;
           int j = 2;
              
           while (j * j <= number_2) 
           {
               if (number_2 % j == 0) 
               {
                   sum_divisor_2 += j;
                    
                   if (j * j != number_2)
                       sum_divisor_2 += number_2 / j;
               }
               j = j + 1;
           }
           if (sum_divisor_2 == number_1 + 1 && 
               number_1 <= n && number_2 <= n)
           {
               Set.add(number_1);
               Set.add(number_2);
           }
       }
    }
       
    // Sum all betrothed 
    // numbers up to N 
    int Summ = 0;
    for(int i = 0; i < Set.size(); i++)
    {
       if (Set.get(i) <= n) 
          Summ += Set.get(i);
    }
    return Summ;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 78;
     
    System.out.println(Betrothed_Sum(n));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to find the
# Sum of the all Betrothed
# numbers up to N
 
import math
 
# Function to find the Sum of
# the all Betrothed numbers
def Betrothed_Sum(n):
     
    # To store the Betrothed
    # numbers
    Set = []
 
    for number_1 in range(1, n):
 
        # Calculate sum of
        # number_1's divisors
 
        # 1 is always a divisor
        sum_divisor_1 = 1
 
        # i = 2 because we don't
        # want to include
        # 1 as a divisor.
        i = 2
 
        while i * i <= number_1:
            if (number_1 % i == 0):
                sum_divisor_1 = sum_divisor_1 + i
 
                if (i * i != number_1):
                    sum_divisor_1 += number_1 // i
            i = i + 1
 
        if (sum_divisor_1 > number_1):
 
            number_2 = sum_divisor_1 - 1
            sum_divisor_2 = 1
            j = 2
            while j * j <= number_2:
                if (number_2 % j == 0):
                    sum_divisor_2 += j
                    if (j * j != number_2):
                        sum_divisor_2 += number_2 // j
                j = j + 1
 
            if (sum_divisor_2 == number_1 + 1
                and number_1<= n and number_2<= n):
                Set.append(number_1)
                Set.append(number_2)
 
    # Sum all Betrothed
    # numbers up to N
    Summ = 0
    for i in Set:
        if i <= n:
            Summ += i
    return Summ
 
 
# Driver Code
n = 78
print(Betrothed_Sum(n))

// C# program to find the sum
// of the all betrothed numbers
// up to N 
using System;
using System.Collections;
 
class GFG{
     
// Function to find the sum of 
// the all betrothed numbers 
public static int Betrothed_Sum(int n)
{
     
    // To store the betrothed 
    // numbers 
    ArrayList set = new ArrayList();
        
    for(int number_1 = 1;
            number_1 < n; 
            number_1++)
    {
         
        // Calculate sum of 
        // number_1's divisors 
        // 1 is always a divisor
        int sum_divisor_1 = 1;
         
        // i = 2 because we don't 
        // want to include 
        // 1 as a divisor. 
        int i = 2;
         
        while (i * i <= number_1)
        {
            if (number_1 % i == 0)
            {
                sum_divisor_1 = sum_divisor_1 + i;
                 
                if (i * i != number_1)
                    sum_divisor_1 += number_1 / i; 
            }
            i ++;
        }
         
        if (sum_divisor_1 > number_1)
        {
            int number_2 = sum_divisor_1 - 1;
            int sum_divisor_2 = 1;
            int j = 2;
             
            while (j * j <= number_2) 
            {
                if (number_2 % j == 0) 
                {
                    sum_divisor_2 += j;
                     
                    if (j * j != number_2)
                        sum_divisor_2 += number_2 / j;
                }
                j = j + 1;
            }
             
            if (sum_divisor_2 == number_1 + 1 && 
                number_1 <= n && number_2 <= n)
            {
                set.Add(number_1);
                set.Add(number_2);
            }
        }
    }
        
    // Sum all betrothed 
    // numbers up to N 
    int Summ = 0;
    for(int i = 0; i < set.Count; i++)
    {
        if ((int)set[i] <= n) 
            Summ += (int)set[i];
    }
    return Summ;
}
 
// Driver code
static public void Main()
{
    int n = 78;
      
    Console.WriteLine(Betrothed_Sum(n));
}
}
 
// This code is contributed by offbeat

<script>
// Javascript program to find the sum of the  
// all betrothed numbers up to N
 
// Function to find the sum of
// the all betrothed numbers
function Betrothed_Sum(n)
{
    // To store the betrothed
    // numbers
    let Set = [];
     
    for(let number_1 = 1; number_1 < n;
                            number_1++)
    {
         
       // Calculate sum of
       // number_1's divisors
       // 1 is always a divisor
       let sum_divisor_1 = 1;
        
       // i = 2 because we don't
       // want to include
       // 1 as a divisor.
       let i = 2;
        
       while (i * i <= number_1)
       {
           if (number_1 % i == 0)
           {
               sum_divisor_1 = sum_divisor_1 + i;
                
               if (i * i != number_1)
                   sum_divisor_1 += parseInt(number_1 / i);
           }
           i++;
       }
       if (sum_divisor_1 > number_1)
       {
           let number_2 = sum_divisor_1 - 1;
           let sum_divisor_2 = 1;
           let j = 2;
            
           while (j * j <= number_2)
           {
               if (number_2 % j == 0)
               {
                   sum_divisor_2 += j;
                   if (j * j != number_2)
                       sum_divisor_2 += parseInt(number_2 / j);
               }
               j = j + 1;
           }
           if ((sum_divisor_2 == number_1 + 1) &&
               number_1 <= n && number_2 <= n)
           {
               Set.push(number_1);
               Set.push(number_2);
           }
       }
    }
     
    // Sum all betrothed
    // numbers up to N
    let Summ = 0;
    for(let i = 0; i < Set.length; i++)
    {
       if(Set[i] <= n)
          Summ += Set[i];
    }
    return Summ;
}
 
// Driver code
    let n = 78;
    document.write(Betrothed_Sum(n));
 
// This code is contributed by rishavmahato348.
</script>

123

Complejidad de tiempo: O(N * sqrt(N))