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

Posted on by Rudeus Greyrat

Dado un número N. Encuentra la suma de todos los números amistosos hasta N. Si A y B son pares amistosos (dos números son amistosos si el primero es igual a la suma de los divisores del segundo), entonces A y B se llaman como Números amistosos. 
Ejemplos: 
 

Entrada: 284 
Salida: 504 
Explicación: 220 y 284 son dos números amistosos hasta 284
Entrada: 250 
Salida: 220 
Explicación: 220 es el único número amistoso

Enfoque : 
un enfoque eficiente es almacenar todos los números amistosos en un conjunto y, para un N dado, sumar todos los números del conjunto que son menores que iguales a N. El siguiente
código es la implementación del enfoque anterior: 
 

C++

// CPP program to find sum of all
// amicable numbers up to n
#include <bits/stdc++.h>
using namespace std;
 
#define N 100005
 
// Function to return all amicable numbers
set<int> AMICABLE()
{
    int sum[N];
    memset(sum, 0, sizeof sum);
    for (int i = 1; i < N; i++) {
 
        // include 1
        sum[i]++;
 
        for (int j = 2; j * j <= i; j++) {
 
            // j is proper divisor of i
            if (i % j == 0) {
                sum[i] += j;
 
                // if i is not a perfect square
                if (i / j != j)
                    sum[i] += i / j;
            }
        }
    }
 
    set<int> s;
    for (int i = 2; i < N; i++) {
 
        // insert amicable numbers
        if (i != sum[i] and sum[i] < N and i == sum[sum[i]]
            and !s.count(i) and !s.count(sum[i])) {
            s.insert(i);
            s.insert(sum[i]);
        }
    }
 
    return s;
}
 
// function to find sum of all
// amicable numbers up to N
int SumOfAmicable(int n)
{
    // to store required sum
    int sum = 0;
 
    // to store all amicable numbers
    set<int> s = AMICABLE();
 
    // sum all amicable numbers upto N
    for (auto i = s.begin(); i != s.end(); ++i) {
        if (*i <= n)
            sum += *i;
        else
            break;
    }
 
    // required answer
    return sum;
}
 
// Driver code to test above functions
int main()
{
    int n = 284;
 
    cout << SumOfAmicable(n);
 
    return 0;
}

Java

// Java program to find sum of all
// amicable numbers up to n
import java.util.*;
class GFG
{
     
static final int N=100005;
 
// Function to return all amicable numbers
static Set<Integer> AMICABLE()
{
    int sum[] = new int[N];
    for(int i = 0; i < N; i++)
        sum[i]=0;
     
    for (int i = 1; i < N; i++) 
    {
 
        // include 1
        sum[i]++;
 
        for (int j = 2; j * j <= i; j++)
        {
 
            // j is proper divisor of i
            if (i % j == 0)
            {
                sum[i] += j;
 
                // if i is not a perfect square
                if (i / j != j)
                    sum[i] += i / j;
            }
        }
    }
 
    Set<Integer> s = new HashSet<Integer>();
    for (int i = 2; i < N; i++)
    {
 
        // insert amicable numbers
        if (i != sum[i] && sum[i] < N && i == sum[sum[i]])
        {
            s.add(i);
            s.add(sum[i]);
        }
    }
    return s;
}
 
// function to find sum of all
// amicable numbers up to N
static int SumOfAmicable(int n)
{
    // to store required sum
    int sum = 0;
 
    // to store all amicable numbers
    Set<Integer> s = AMICABLE();
     
     
    // sum all amicable numbers upto N
    for (Integer x : s)
    {
        if (x <= n)
            sum += x;
    }
 
    // required answer
    return sum;
}
 
// Driver code
public static void main(String args[])
{
    int n = 284;
    System.out.println( SumOfAmicable(n));
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to findSum of all
# amicable numbers up to n
import math as mt
 
N = 100005
 
# Function to return all amicable numbers
def AMICABLE():
 
    Sum = [0 for i in range(N)]
     
    for i in range(1, N):
        Sum[i] += 1
 
        for j in range(2, mt.ceil(mt.sqrt(i))):
 
            # j is proper divisor of i
            if (i % j == 0):
                Sum[i] += j
 
                # if i is not a perfect square
                if (i // j != j):
                    Sum[i] += i // j
 
    s = set()
    for i in range(2, N):
        if(i != Sum[i] and Sum[i] < N and
           i == Sum[Sum[i]] and i not in s and
                Sum[i] not in s):
            s.add(i)
            s.add(Sum[i])
 
    return s
 
# function to findSum of all amicable
# numbers up to N
def SumOfAmicable(n):
 
    # to store requiredSum
    Sum = 0
 
    # to store all amicable numbers
    s = AMICABLE()
 
    #Sum all amicable numbers upto N
    s = sorted(s)
    for i in s:
        if (i <= n):
            Sum += i
        else:
            break
     
    # required answer
    return Sum
 
# Driver Code
n = 284
print(SumOfAmicable(n))
 
# This code is contributed by
# mohit kumar 29

C#

// C# program to find sum of all
// amicable numbers up to n
using System;
using System.Collections.Generic;
 
class GFG
{
     
static readonly int N = 100005;
 
// Function to return all amicable numbers
static HashSet<int> AMICABLE()
{
    int []sum = new int[N];
    for(int i = 0; i < N; i++)
        sum[i] = 0;
     
    for (int i = 1; i < N; i++)
    {
 
        // include 1
        sum[i]++;
 
        for (int j = 2; j * j <= i; j++)
        {
 
            // j is proper divisor of i
            if (i % j == 0)
            {
                sum[i] += j;
 
                // if i is not a perfect square
                if (i / j != j)
                    sum[i] += i / j;
            }
        }
    }
 
    HashSet<int> s = new HashSet<int>();
    for (int i = 2; i < N; i++)
    {
 
        // insert amicable numbers
        if (i != sum[i] && sum[i] < N &&
                            i == sum[sum[i]])
        {
            s.Add(i);
            s.Add(sum[i]);
        }
    }
    return s;
}
 
// function to find sum of all
// amicable numbers up to N
static int SumOfAmicable(int n)
{
    // to store required sum
    int sum = 0;
 
    // to store all amicable numbers
    HashSet<int> s = AMICABLE();
     
     
    // sum all amicable numbers upto N
    foreach (int x in s)
    {
        if (x <= n)
            sum += x;
    }
 
    // required answer
    return sum;
}
 
// Driver code
public static void Main()
{
    int n = 284;
    Console.WriteLine( SumOfAmicable(n));
}
}
 
/* This code contributed by PrinciRaj1992 */

PHP

<?php
// PHP program to find sum of all
// amicable numbers up to n
$N = 10005;
 
// Function to return all amicable
// numbers
function AMICABLE()
{
    global $N;
    $sum = array_fill(0, $N, 0);
    for ($i = 1; $i < $N; $i++)
    {
 
        // include 1
        $sum[$i]++;
 
        for ($j = 2; $j * $j <= $i; $j++)
        {
 
            // j is proper divisor of i
            if ($i % $j == 0)
            {
                $sum[$i] += $j;
 
                // if i is not a perfect square
                if ($i / $j != $j)
                    $sum[$i] += $i / $j;
            }
        }
    }
 
    $s = array();
    for ($i = 2; $i < $N; $i++)
    {
 
        // insert amicable numbers
        if ($i != $sum[$i] and $sum[$i] < $N and
                        $i == $sum[$sum[$i]] and
                           !in_array($i, $s) and
                           !in_array($sum[$i], $s))
        {
            array_push($s, $i);
            array_push($s, $sum[$i]);
        }
    }
 
    return $s;
}
 
// function to find sum of all
// amicable numbers up to N
function SumOfAmicable($n)
{
    // to store required sum
    $sum = 0;
 
    // to store all amicable numbers
    $s = AMICABLE();
    $s = array_unique($s);
    sort($s);
     
    // sum all amicable numbers upto N
    for ($i = 0; $i != count($s); ++$i)
    {
        if ($s[$i] <= $n)
            $sum += $s[$i];
        else
            break;
    }
     
    // required answer
    return $sum;
}
 
// Driver code
$n = 284;
 
echo SumOfAmicable($n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// JavaScript program to find sum of all
// amicable numbers up to n
 
let N=100005;
 
// Function to return all amicable numbers
function  AMICABLE()
{
    let sum = new Array(N);
    for(let i = 0; i < N; i++)
        sum[i]=0;
       
    for (let i = 1; i < N; i++) 
    {
   
        // include 1
        sum[i]++;
   
        for (let j = 2; j * j <= i; j++)
        {
   
            // j is proper divisor of i
            if (i % j == 0)
            {
                sum[i] += j;
   
                // if i is not a perfect square
                if (i / j != j)
                    sum[i] += i / j;
            }
        }
    }
   
    let s = new Set();
    for (let i = 2; i < N; i++)
    {
   
        // insert amicable numbers
        if (i != sum[i] && sum[i] < N && i == sum[sum[i]])
        {
            s.add(i);
            s.add(sum[i]);
        }
    }
    return s;
}
 
// function to find sum of all
// amicable numbers up to N
function SumOfAmicable(n)
{
    // to store required sum
    let sum = 0;
   
    // to store all amicable numbers
    let s = AMICABLE();
       
       
    // sum all amicable numbers upto N
    for (let x of s.values())
    {
        if (x <= n)
            sum += x;
    }
   
    // required answer
    return sum;
}
 
// Driver code
let n = 284;
document.write( SumOfAmicable(n));
 
 
// This code is contributed by unknown2108
 
</script>
Producción: 

504

 

Complejidad temporal: O(n 2 )

Espacio Auxiliar: O(100005)

Publicación traducida automáticamente

Artículo escrito por pawan_asipu 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 *