Dado un número natural n , la tarea es encontrar la suma de los divisores de todos los divisores de n.
Ejemplos:
Input : n = 54 Output : 232 Divisors of 54 = 1, 2, 3, 6, 9, 18, 27, 54. Sum of divisors of 1, 2, 3, 6, 9, 18, 27, 54 are 1, 3, 4, 12, 13, 39, 40, 120 respectively. Sum of divisors of all the divisors of 54 = 1 + 3 + 4 + 12 + 13 + 39 + 40 + 120 = 232. Input : n = 10 Output : 28 Divisors of 10 are 1, 2, 5, 10 Sums of divisors of divisors are 1, 3, 6, 18. Overall sum = 1 + 3 + 6 + 18 = 28
Usando el hecho de que cualquier número n puede expresarse como producto de factores primos, n = p 1 k1 xp 2 k2 x … donde p 1 , p 2 , … son números primos.
Todos los divisores de n se pueden expresar como p 1 a xp 2 b x …, donde 0 <= a <= k1 y 0 <= b <= k2.
Ahora la suma de los divisores será la suma de todas las potencias de p 1 – p 1 0 , p 1 1 ,…., p 1 k1 multiplicada por todas las potencias de p 2 – p 2 0 , p 21 ,…., p 2 k1
Suma del Divisor de n
= (p 1 0 xp 2 0 ) + (p 1 1 xp 2 0 ) +…..+ (p 1 k1 xp 2 0 ) +….+ (p 1 0 xp 2 1 ) + (p 1 1 xp 2 1 ) +…..+ (p 1 k1 xp 2 1 ) +……..+
(p 1 0 xp 2 k2 ) + (p 1 1 xp 2k2 ) +……+ (p 1 k1 xp 2 k2 ).
= (p 1 0 + p 1 1 +…+ p 1 k1 ) xp 2 0 + (p 1 0 + p 1 1 +…+ p 1 k1 ) xp 2 1 +…….+ (p 1 0 + p 1 1 +…+ p 1 k1 ) xp 2 k2 .
= (p 1 0 + p 1 1 +…+ p 1 k1 ) x (p2 0 + p 2 1 +…+ p 2 k2 ).
Ahora, los divisores de cualquier p a , para p como primo, son p 0 , p 1 ,……, p a . Y la suma de los divisores será (p (a+1) – 1)/(p -1), defina por f(p).
Entonces, la suma de los divisores de todos los divisores será,
= (f(p 1 0 ) + f(p 1 1 ) +…+ f(p 1 k1 )) x (f(p 2 0 ) + f(p 2 1 ) +…+ f(p 2 k2 )).
Entonces, dado un número n, por descomposición en factores primos podemos encontrar la suma de los divisores de todos los divisores. Pero en este problema se nos da que n es producto de elemento de array. Entonces, encuentre la descomposición en factores primos de cada elemento y usando el hecho de a b xa c = a b+c .
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find sum of divisors of all
// the divisors of a natural number.
#include<bits/stdc++.h>
using namespace std;
// Returns sum of divisors of all the divisors
// of n
int sumDivisorsOfDivisors(int n)
{
// Calculating powers of prime factors and
// storing them in a map mp[].
map<int, int> mp;
for (int j=2; j<=sqrt(n); j++)
{
int count = 0;
while (n%j == 0)
{
n /= j;
count++;
}
if (count)
mp[j] = count;
}
// If n is a prime number
if (n != 1)
mp[n] = 1;
// For each prime factor, calculating (p^(a+1)-1)/(p-1)
// and adding it to answer.
int ans = 1;
for (auto it : mp)
{
int pw = 1;
int sum = 0;
for (int i=it.second+1; i>=1; i--)
{
sum += (i*pw);
pw *= it.first;
}
ans *= sum;
}
return ans;
}
// Driven Program
int main()
{
int n = 10;
cout << sumDivisorsOfDivisors(n);
return 0;
}
Java
// Java program to find sum of divisors of all
// the divisors of a natural number.
import java.util.HashMap;
class GFG
{
// Returns sum of divisors of all the divisors
// of n
public static int sumDivisorsOfDivisors(int n)
{
// Calculating powers of prime factors and
// storing them in a map mp[].
HashMap<Integer, Integer> mp = new HashMap<>();
for (int j = 2; j <= Math.sqrt(n); j++)
{
int count = 0;
while (n % j == 0)
{
n /= j;
count++;
}
if (count != 0)
mp.put(j, count);
}
// If n is a prime number
if (n != 1)
mp.put(n, 1);
// For each prime factor, calculating (p^(a+1)-1)/(p-1)
// and adding it to answer.
int ans = 1;
for (HashMap.Entry<Integer, Integer> entry : mp.entrySet())
{
int pw = 1;
int sum = 0;
for (int i = entry.getValue() + 1; i >= 1; i--)
{
sum += (i * pw);
pw *= entry.getKey();
}
ans *= sum;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int n = 10;
System.out.println(sumDivisorsOfDivisors(n));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to find sum of divisors # of all the divisors of a natural number. import math as mt # Returns sum of divisors of all # the divisors of n def sumDivisorsOfDivisors(n): # Calculating powers of prime factors # and storing them in a map mp[]. mp = dict() for j in range(2, mt.ceil(mt.sqrt(n))): count = 0 while (n % j == 0): n //= j count += 1 if (count): mp[j] = count # If n is a prime number if (n != 1): mp[n] = 1 # For each prime factor, calculating # (p^(a+1)-1)/(p-1) and adding it to answer. ans = 1 for it in mp: pw = 1 summ = 0 for i in range(mp[it] + 1, 0, -1): summ += (i * pw) pw *= it ans *= summ return ans # Driver Code n = 10 print(sumDivisorsOfDivisors(n)) # This code is contributed # by mohit kumar 29
C#
// C# program to find sum of divisors of all
// the divisors of a natural number.
using System;
using System.Collections.Generic;
class GFG
{
// Returns sum of divisors of
// all the divisors of n
public static int sumDivisorsOfDivisors(int n)
{
// Calculating powers of prime factors and
// storing them in a map mp[].
Dictionary<int,
int> mp = new Dictionary<int,
int>();
for (int j = 2; j <= Math.Sqrt(n); j++)
{
int count = 0;
while (n % j == 0)
{
n /= j;
count++;
}
if (count != 0)
mp.Add(j, count);
}
// If n is a prime number
if (n != 1)
mp.Add(n, 1);
// For each prime factor,
// calculating (p^(a+1)-1)/(p-1)
// and adding it to answer.
int ans = 1;
foreach(KeyValuePair<int, int> entry in mp)
{
int pw = 1;
int sum = 0;
for (int i = entry.Value + 1;
i >= 1; i--)
{
sum += (i * pw);
pw = entry.Key;
}
ans *= sum;
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int n = 10;
Console.WriteLine(sumDivisorsOfDivisors(n));
}
}
// This code is contributed
// by Princi Singh
Javascript
<script>
// Javascript program to find sum of divisors of all
// the divisors of a natural number.
// Returns sum of divisors of all the divisors
// of n
function sumDivisorsOfDivisors(n)
{
// Calculating powers of prime factors and
// storing them in a map mp[].
let mp = new Map();
for (let j = 2; j <= Math.sqrt(n); j++)
{
let count = 0;
while (n % j == 0)
{
n = Math.floor(n/j);
count++;
}
if (count != 0)
mp.set(j, count);
}
// If n is a prime number
if (n != 1)
mp.set(n, 1);
// For each prime factor, calculating (p^(a+1)-1)/(p-1)
// and adding it to answer.
let ans = 1;
for (let [key, value] of mp.entries())
{
let pw = 1;
let sum = 0;
for (let i = value + 1; i >= 1; i--)
{
sum += (i * pw);
pw = key;
}
ans *= sum;
}
return ans;
}
// Driver code
let n = 10;
document.write(sumDivisorsOfDivisors(n));
// This code is contributed by patel2127
</script>
Producción:
28
Complejidad de Tiempo: O(√n log n)
Espacio Auxiliar: O(n)
Optimizaciones:
para los casos en los que hay múltiples entradas para las que necesitamos encontrar el valor, podemos usar Sieve of Eratosthenes como se explica en esta publicación.
Este artículo es una contribución de Aarti_Rathi y Anuj Chauhan . 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA