Dado un número n, la tarea es encontrar la suma de todos los factores.
Ejemplos:
Input : n = 30
Output : 72
Dividers sum 1 + 2 + 3 + 5 + 6 +
10 + 15 + 30 = 72
Input : n = 15
Output : 24
Dividers sum 1 + 3 + 5 + 15 = 24
Una solución simple es atravesar todos los divisores y sumarlos.
C++
// Simple C++ program to
// find sum of all divisors
// of a natural number
#include<bits/stdc++.h>
using namespace std;
// Function to calculate sum of all
//divisors of a given number
int divSum(int n)
{
if(n == 1)
return 1;
// Sum of divisors
int result = 0;
// find all divisors which divides 'num'
for (int i = 2; i <= sqrt(n); i++)
{
// if 'i' is divisor of 'n'
if (n % i == 0)
{
// if both divisors are same
// then add it once else add
// both
if (i == (n / i))
result += i;
else
result += (i + n/i);
}
}
// Add 1 and n to result as above loop
// considers proper divisors greater
// than 1.
return (result + n + 1);
}
// Driver program to run the case
int main()
{
int n = 30;
cout << divSum(n);
return 0;
}
Java
// Simple Java program to
// find sum of all divisors
// of a natural number
import java.io.*;
class GFG {
// Function to calculate sum of all
//divisors of a given number
static int divSum(int n)
{
if(n == 1)
return 1;
// Final result of summation
// of divisors
int result = 0;
// find all divisors which divides 'num'
for (int i = 2; i <= Math.sqrt(n); i++)
{
// if 'i' is divisor of 'n'
if (n % i == 0)
{
// if both divisors are same
// then add it once else add
// both
if (i == (n / i))
result += i;
else
result += (i + n / i);
}
}
// Add 1 and n to result as above loop
// considers proper divisors greater
// than 1.
return (result + n + 1);
}
// Driver program to run the case
public static void main(String[] args)
{
int n = 30;
System.out.println(divSum(n));
}
}
// This code is contributed by Prerna Saini.
Python3
# Simple Python 3 program to # find sum of all divisors of # a natural number import math # Function to calculate sum # of all divisors of given # natural number def divSum(n) : if(n == 1): return 1 # Final result of summation # of divisors result = 0 # find all divisors which # divides 'num' for i in range(2,(int)(math.sqrt(n))+1) : # if 'i' is divisor of 'n' if (n % i == 0) : # if both divisors are same # then add it only once # else add both if (i == (n/i)) : result = result + i else : result = result + (i + n//i) # Add 1 and n to result as above # loop considers proper divisors # greater than 1. return (result + n + 1) # Driver program to run the case n = 30 print(divSum(n)) # This code is contributed by Nikita Tiwari.
C#
// Simple C# program to
// find sum of all divisors
// of a natural number
using System;
class GFG {
// Function to calculate sum of all
//divisors of a given number
static int divSum(int n)
{
if(n == 1)
return 1;
// Final result of summation
// of divisors
int result = 0;
// find all divisors which divides 'num'
for (int i = 2; i <= Math.Sqrt(n); i++)
{
// if 'i' is divisor of 'n'
if (n % i == 0)
{
// if both divisors are same
// then add it once else add
// both
if (i == (n / i))
result += i;
else
result += (i + n / i);
}
}
// Add 1 and n to result as above loop
// considers proper divisors greater
// than 1.
return (result + n + 1);
}
// Driver program to run the case
public static void Main()
{
int n = 30;
Console.WriteLine(divSum(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// Find sum of all divisors
// of a natural number
// Function to calculate sum of all
//divisors of a given number
function divSum($n)
{
if($n == 1)
return 1;
// Sum of divisors
$result = 0;
// find all divisors
// which divides 'num'
for ( $i = 2; $i <= sqrt($n); $i++)
{
// if 'i' is divisor of 'n'
if ($n % $i == 0)
{
// if both divisors are same
// then add it once else add
// both
if ($i == ($n / $i))
$result += $i;
else
$result += ($i + $n / $i);
}
}
// Add 1 and n to result as
// above loop considers proper
// divisors greater than 1.
return ($result + $n + 1);
}
// Driver Code
$n = 30;
echo divSum($n);
// This code is contributed by SanjuTomar.
?>
Javascript
<script>
// Find sum of all divisors
// of a natural number
// Function to calculate sum of all
//divisors of a given number
function divSum(n)
{
if(n == 1)
return 1;
// Sum of divisors
let result = 0;
// find all divisors
// which divides 'num'
for ( let i = 2; i <= Math.sqrt(n); i++)
{
// if 'i' is divisor of 'n'
if (n % i == 0)
{
// if both divisors are same
// then add it once else add
// both
if (i == (n / i))
result += i;
else
result += (i + n / i);
}
}
// Add 1 and n to result as
// above loop considers proper
// divisors greater than 1.
return (result + n + 1);
}
// Driver Code
let n = 30;
document.write(divSum(n));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción :
72
Complejidad temporal: O(√n)
Espacio auxiliar: O(1)
Una solución eficiente es usar la siguiente fórmula.
Sean p 1 , p 2 , … p k factores primos de n. Sean a 1 , a 2 , .. a k potencias máximas de p 1 , p 2 , .. p k respectivamente que dividen n, es decir, podemos escribir n como n = (p 1 a 1 )*(p 2 a 2 )* … (p k a k ) .
Sum of divisors = (1 + p1 + p12 ... p1a1) *
(1 + p2 + p22 ... p2a2) *
.............................................
(1 + pk + pk2 ... pkak)
We can notice that individual terms of above
formula are Geometric Progressions (GP). We
can rewrite the formula as.
Sum of divisors = (p1a1+1 - 1)/(p1 -1) *
(p2a2+1 - 1)/(p2 -1) *
..................................
(pkak+1 - 1)/(pk -1)
¿Cómo funciona la fórmula anterior?
Consider the number 18.
Sum of factors = 1 + 2 + 3 + 6 + 9 + 18
Writing divisors as powers of prime factors.
Sum of factors = (20)(30) + (21)(30) + (2^0)(31) +
(21)(31) + (20)(3^2) + (2^1)(32)
= (20)(30) + (2^0)(31) + (2^0)(32) +
(21)(3^0) + (21)(31) + (21)(32)
= (20)(30 + 31 + 32) +
(21)(30 + 31 + 32)
= (20 + 21)(30 + 31 + 32)
If we take a closer look, we can notice that the
above expression is in the form.
(1 + p1) * (1 + p2 + p22)
Where p1 = 2 and p2 = 3 and 18 = 2132
Entonces la tarea se reduce a encontrar todos los factores primos y sus potencias.
C++
// Formula based CPP program to
// find sum of all divisors of n.
#include <bits/stdc++.h>
using namespace std;
// Returns sum of all factors of n.
int sumofFactors(int n)
{
// Traversing through all prime factors.
int res = 1;
for (int i = 2; i <= sqrt(n); i++)
{
int curr_sum = 1;
int curr_term = 1;
while (n % i == 0) {
// THE BELOW STATEMENT MAKES
// IT BETTER THAN ABOVE METHOD
// AS WE REDUCE VALUE OF n.
n = n / i;
curr_term *= i;
curr_sum += curr_term;
}
res *= curr_sum;
}
// This condition is to handle
// the case when n is a prime
// number greater than 2.
if (n >= 2)
res *= (1 + n);
return res;
}
// Driver code
int main()
{
int n = 30;
cout << sumofFactors(n);
return 0;
}
Java
// Formula based Java program to
// find sum of all divisors of n.
import java.io.*;
import java.math.*;
public class GFG{
// Returns sum of all factors of n.
static int sumofFactors(int n)
{
// Traversing through all prime factors.
int res = 1;
for (int i = 2; i <= Math.sqrt(n); i++)
{
int curr_sum = 1;
int curr_term = 1;
while (n % i == 0)
{
// THE BELOW STATEMENT MAKES
// IT BETTER THAN ABOVE METHOD
// AS WE REDUCE VALUE OF n.
n = n / i;
curr_term *= i;
curr_sum += curr_term;
}
res *= curr_sum;
}
// This condition is to handle
// the case when n is a prime
// number greater than 2
if (n > 2)
res *= (1 + n);
return res;
}
// Driver code
public static void main(String args[])
{
int n = 30;
System.out.println(sumofFactors(n));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Formula based Python3 code to find
# sum of all divisors of n.
import math as m
# Returns sum of all factors of n.
def sumofFactors(n):
# Traversing through all
# prime factors
res = 1
for i in range(2, int(m.sqrt(n) + 1)):
curr_sum = 1
curr_term = 1
while n % i == 0:
n = n / i;
curr_term = curr_term * i;
curr_sum += curr_term;
res = res * curr_sum
# This condition is to handle the
# case when n is a prime number
# greater than 2
if n > 2:
res = res * (1 + n)
return res;
# driver code
sum = sumofFactors(30)
print ("Sum of all divisors is: ",sum)
# This code is contributed by Saloni Gupta
C#
// Formula based Java program to
// find sum of all divisors of n.
using System;
public class GFG {
// Returns sum of all factors of n.
static int sumofFactors(int n)
{
// Traversing through all prime factors.
int res = 1;
for (int i = 2; i <= Math.Sqrt(n); i++)
{
int curr_sum = 1;
int curr_term = 1;
while (n % i == 0)
{
// THE BELOW STATEMENT MAKES
// IT BETTER THAN ABOVE METHOD
// AS WE REDUCE VALUE OF n.
n = n / i;
curr_term *= i;
curr_sum += curr_term;
}
res *= curr_sum;
}
// This condition is to handle
// the case when n is a prime
// number greater than 2
if (n > 2)
res *= (1 + n);
return res;
}
// Driver code
public static void Main()
{
int n = 30;
Console.WriteLine(sumofFactors(n));
}
}
/*This code is contributed by vt_m.*/
PHP
<?php
// Formula based PHP program to
// find sum of all divisors of n.
// Returns sum of all factors of n.
function sumofFactors($n)
{
// Traversing through
// all prime factors.
$res = 1;
for ($i = 2; $i <= sqrt($n); $i++)
{
$curr_sum = 1;
$curr_term = 1;
while ($n % $i == 0)
{
// THE BELOW STATEMENT MAKES
// IT BETTER THAN ABOVE METHOD
// AS WE REDUCE VALUE OF n.
$n = $n / $i;
$curr_term *= $i;
$curr_sum += $curr_term;
}
$res *= $curr_sum;
}
// This condition is to handle
// the case when n is a prime
// number greater than 2
if ($n > 2)
$res *= (1 + $n);
return $res;
}
// Driver Code
$n = 30;
echo sumofFactors($n);
// This code is contributed by Anuj_67.
?>
Javascript
<script>
// Formula based Javascript program to
// find sum of all divisors of n.
// Returns sum of all factors of n.
function sumofFactors(n)
{
// Traversing through
// all prime factors.
let res = 1;
for (let i = 2; i <= Math.sqrt(n); i++)
{
let curr_sum = 1;
let curr_term = 1;
while (n % i == 0)
{
// THE BELOW STATEMENT MAKES
// IT BETTER THAN ABOVE METHOD
// AS WE REDUCE VALUE OF n.
n = n / i;
curr_term *= i;
curr_sum += curr_term;
}
res *= curr_sum;
}
// This condition is to handle
// the case when n is a prime
// number greater than 2
if (n > 2)
res *= (1 + n);
return res;
}
// Driver Code
let n = 30;
document.write(sumofFactors(n));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción :
72
Complejidad de Tiempo: O(√n log n)
Espacio Auxiliar: O(1)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Optimización adicional.
Si hay múltiples consultas, podemos usar Sieve para encontrar factores primos y sus potencias .
Referencias:
https://www.math.upenn.edu/~deturck/m170/wk3/lecture/sumdiv.html
http://mathforum.org/library/drmath/view/71550.html
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA