Suma de todos los divisores propios de números naturales en una array

Dada una array de números naturales, cuente la suma de sus divisores propios para cada elemento de la array.
 

Input  : int arr[] = {8, 13, 24, 36, 59, 75, 87}
Output : 7 1 36 55 1 49 21
Number 8 has 3 proper divisors 1, 2, 4
and their sum comes out to be 7.

Una solución ingenua a este problema se ha discutido en la publicación a continuación. 
Suma de todos los divisores propios de un número natural
Podemos hacer esto de manera más eficiente haciendo uso de la criba de Eratóstenes .
La idea se basa en la descomposición en factores primos de un número. Usando tamiz podemos almacenar todos los factores primos de un número y sus potencias .
 

To find all divisors, we need to consider
all powers of a prime factor and multiply
it with all powers of other prime factors.
(For example, if the number is 36, its prime
factors are 2 and 3 and all divisors are 1,
2, 3, 4, 6, 9, 12 and 18.

Consider a number N can be written 
as P1^Q1 * P2^Q2 * P3^Q3 (here only 3 
prime factors are considered but there can 
be more than that) then sum of its divisors 
will be written as:
 = P1^0 * P2^0 * P3^0 + P1^0 * P2^0 * P3^1 + 
   P1^0 * P2^0 * P3^2 + ................ + 
   P1^0 * P2^0 * P3^Q3 + P1^0 * P2^1 * P3^0 + 
   P1^0 * P2^1 * P3^1 + P1^0 * P2^1 * P3^2 + 
   ................ + P1^0 * P2^1 * P3^Q3 +
   .
   .
   .
   P1^Q1 * P2^Q2 * P3^0 + P1^Q1 * P2^Q2 * P3^1 + 
   P1^Q1 * P2^Q2 * P3^2 + .......... + 
   P1^Q1 * P2^Q2 * P3^Q3

Above can be written as,
(((P1^(Q1+1)) - 1) / 
  (P1 - 1)) * (((P2^(Q2+1)) - 1) / 
  (P2 - 1)) * (((P3^(Q3 + 1)) - 1) / 
  (P3 - 1))

A continuación se muestra la implementación basada en la fórmula anterior. 
 

// C++ program to find sum of proper divisors for
// every element in an array.
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000001
#define pii pair<int, int>
#define F first
#define S second
 
// To store prime factors and their
// powers
vector<pii> factors[MAX];
 
// Fills factors such that factors[i] is
// a vector of pairs containing prime factors
// (of i) and their powers.
// Also sets values in isPrime[]
void sieveOfEratothenese()
{
    // To check if a number is prime
    bool isPrime[MAX];
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
 
    for (int i = 2; i < MAX; i++)
    {
        // If i is prime, then update its
        // powers in all multiples of it.
        if (isPrime[i])
        {
            for (int j = i; j < MAX; j += i)
            {
                int k, l;
                isPrime[j] = false;
                for (k = j, l = 0; k % i == 0; l++, k /= i)
                    ;
                factors[j].push_back(make_pair(i, l));
            }
        }
    }
}
 
// Returns sum of proper divisors of num
// using factors[]
int sumOfProperDivisors(int num)
{
    // Applying above discussed formula for every
    // array element
    int mul = 1;
    for (int i = 0; i < factors[num].size(); i++)
        mul *= ((pow(factors[num][i].F,
                     factors[num][i].S + 1) - 1) /
                (factors[num][i].F - 1));
    return mul - num;
}
 
// Driver code
int main()
{
    sieveOfEratothenese();
    int arr[] = { 8, 13, 24, 36, 59, 75, 91 };
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
        cout << sumOfProperDivisors(arr[i]) << " ";
    cout << endl;
    return 0;
}

// Java program to find sum of proper divisors for
// every element in an array.
import java.util.*;
 
class GFG
{
     
static final int MAX = 100001;
 
static class pair
{
    int F, S;
 
    public pair(int f, int s) {
        F = f;
        S = s;
    }
     
}
// To store prime factors and their
// powers
static Vector<pair> []factors = new Vector[MAX];
 
// Fills factors such that factors[i] is
// a vector of pairs containing prime factors
// (of i) and their powers.
// Also sets values in isPrime[]
static void sieveOfEratothenese()
{
    // To check if a number is prime
    boolean []isPrime = new boolean[MAX];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
 
    for (int i = 2; i < MAX; i++)
    {
        // If i is prime, then update its
        // powers in all multiples of it.
        if (isPrime[i])
        {
            for (int j = i; j < MAX; j += i)
            {
                int k, l;
                isPrime[j] = false;
                for (k = j, l = 0; k % i == 0; l++, k /= i)
                    ;
                factors[j].add(new pair(i, l));
            }
        }
    }
}
 
// Returns sum of proper divisors of num
// using factors[]
static int sumOfProperDivisors(int num)
{
    // Applying above discussed formula for every
    // array element
    int mul = 1;
    for (int i = 0; i < factors[num].size(); i++)
        mul *= ((Math.pow(factors[num].get(i).F,
                    factors[num].get(i).S + 1) - 1) /
                (factors[num].get(i).F - 1));
    return mul - num;
}
 
// Driver code
public static void main(String[] args)
{
    for (int i = 0; i < MAX; i++)
        factors[i] = new Vector<pair>();
    sieveOfEratothenese();
    int arr[] = { 8, 13, 24, 36, 59, 75, 91 };
    for (int i = 0; i < arr.length; i++)
        System.out.print(sumOfProperDivisors(arr[i])+ " ");
    System.out.println();
}
}
 
// This code is contributed by 29AjayKumar

# Python program to find sum of proper divisors for
# every element in an array.
import math
 
MAX = 100001
class pair:
    def __init__(self, f, s):
        self.F = f
        self.S = s
 
# To store prime factors and their
# powers
factors = [0 for i in range(MAX)]
 
# Fills factors such that factors[i] is
# a vector of pairs containing prime factors
# (of i) and their powers.
# Also sets values in isPrime[]
def sieveOfEratothenese():
   
    # To check if a number is prime
    global MAX
    isPrime = [0 for i in range(MAX)]
    for i in range(MAX):
        isPrime[i] = True
    isPrime[0] = isPrime[1] = False
   
    for i in range(2, MAX):
        # If i is prime, then update its
        # powers in all multiples of it.
        if (isPrime[i]):
            for j in range(i,MAX,i):
                isPrime[j] = False
                k = j
                l = 0
                while(k % i == 0):
                    l += 1
                    k = k//i
                factors[j].append(pair(i, l))
 
# Returns sum of proper divisors of num
# using factors[]
def sumOfProperDivisors(num):
    # Applying above discussed formula for every
    # array element
    mul = 1
    for i in range(len(factors[num])):
        mul *= math.floor((math.pow(factors[num][i].F,factors[num][i].S + 1) - 1) // (factors[num][i].F - 1))
    return mul - num
 
# Driver code
for i in range(MAX):
    factors[i] = []
sieveOfEratothenese()
arr = [ 8, 13, 24, 36, 59, 75, 91 ]
for i in range(len(arr)):
    print(sumOfProperDivisors(arr[i]), end = " ")
print()
     
# This code is contributed by shinjanpatra

// C# program to find sum of proper divisors for
// every element in an array.
using System;
using System.Collections.Generic;
 
class GFG
{
     
static readonly int MAX = 100001;
 
class pair
{
    public int F, S;
 
    public pair(int f, int s)
    {
        F = f;
        S = s;
    }
     
}
 
// To store prime factors and their
// powers
static List<pair> []factors = new List<pair>[MAX];
 
// Fills factors such that factors[i] is
// a vector of pairs containing prime factors
// (of i) and their powers.
// Also sets values in isPrime[]
static void sieveOfEratothenese()
{
    // To check if a number is prime
    bool []isPrime = new bool[MAX];
    for (int i = 0; i < MAX; i++)
        isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;
 
    for (int i = 2; i < MAX; i++)
    {
        // If i is prime, then update its
        // powers in all multiples of it.
        if (isPrime[i])
        {
            for (int j = i; j < MAX; j += i)
            {
                int k, l;
                isPrime[j] = false;
                for (k = j, l = 0; k % i == 0; l++, k /= i)
                    ;
                factors[j].Add(new pair(i, l));
            }
        }
    }
}
 
// Returns sum of proper divisors of num
// using factors[]
static int sumOfProperDivisors(int num)
{
    // Applying above discussed formula for every
    // array element
    int mul = 1;
    for (int i = 0; i < factors[num].Count; i++)
        mul *= (int)((Math.Pow(factors[num][i].F,
                    factors[num][i].S + 1) - 1) /
                (factors[num][i].F - 1));
    return mul - num;
}
 
// Driver code
public static void Main(String[] args)
{
    for (int i = 0; i < MAX; i++)
        factors[i] = new List<pair>();
    sieveOfEratothenese();
    int []arr = { 8, 13, 24, 36, 59, 75, 91 };
    for (int i = 0; i < arr.Length; i++)
        Console.Write(sumOfProperDivisors(arr[i])+ " ");
    Console.WriteLine();
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to find sum of proper divisors for
// every element in an array.
 
let MAX = 100001;
class pair
{
    constructor(f,s)
    {
        this.F = f;
           this.S = s;
    }
}
 
// To store prime factors and their
// powers
let factors = new Array(MAX);
 
// Fills factors such that factors[i] is
// a vector of pairs containing prime factors
// (of i) and their powers.
// Also sets values in isPrime[]
function sieveOfEratothenese()
{
    // To check if a number is prime
    let isPrime = new Array(MAX);
    for(let i=0;i<MAX;i++)
    {
        isPrime[i]=true;
    }
    isPrime[0] = isPrime[1] = false;
   
    for (let i = 2; i < MAX; i++)
    {
        // If i is prime, then update its
        // powers in all multiples of it.
        if (isPrime[i])
        {
            for (let j = i; j < MAX; j += i)
            {
                let k, l;
                isPrime[j] = false;
                for (k = j, l = 0; k % i == 0; l++, k = Math.floor(k/i))
                    ;
                factors[j].push(new pair(i, l));
            }
        }
    }
}
 
// Returns sum of proper divisors of num
// using factors[]
function sumOfProperDivisors(num)
{
    // Applying above discussed formula for every
    // array element
    let mul = 1;
    for (let i = 0; i < factors[num].length; i++)
        mul *= Math.floor((Math.pow(factors[num][i].F,
        factors[num][i].S + 1) - 1) / (factors[num][i].F - 1));
    return mul - num;
}
 
// Driver code
for (let i = 0; i < MAX; i++)
    factors[i] = [];
sieveOfEratothenese();
let arr = [ 8, 13, 24, 36, 59, 75, 91 ];
for (let i = 0; i < arr.length; i++)
    document.write(sumOfProperDivisors(arr[i])+ " ");
document.write("<br>");
     
// This code is contributed by rag2127
 
</script>

Producción:  

7 1 36 55 1 49 21

Este artículo es una contribución de Shubham Singh (singh_8) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.