Dado un número natural, calcula la suma de todos sus divisores propios. Un divisor propio de un número natural es el divisor que es estrictamente menor que el número.
Por ejemplo , el número 20 tiene 5 divisores propios: 1, 2, 4, 5, 10, y la suma de divisores es: 1 + 2 + 4 + 5 + 10 = 22.
Ejemplos:
Input : num = 10 Output: 8 // proper divisors 1 + 2 + 5 = 8 Input : num = 36 Output: 55 // proper divisors 1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 = 55
Este problema tiene una solución muy simple , todos sabemos que para cualquier número ‘num’ todos sus divisores son siempre menores e iguales a ‘num/2’ y todos los factores primos son siempre menores e iguales a sqrt(num) . Así que iteramos a través de ‘i’ hasta i<=sqrt(num) y para cualquier ‘i’ si divide ‘num’ , entonces obtenemos dos divisores ‘i’ y ‘num/i’ , agregamos continuamente estos divisores pero para algunos los divisores de números ‘i’ y ‘num/i’ serán iguales en este caso, solo agregue un divisor, por ejemplo; num=36 entonces para i=6 obtendremos (num/i)=6 , es por eso que lo haremos en 6 en la suma solo una vez. Finalmente sumamos uno como uno es divisor de todos los números naturales.
C++
// 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 proper divisors // num --> given natural number int divSum(int num) { // Final result of summation of divisors int result = 0; if(num == 1) // there will be no proper divisor return result; // find all divisors which divides 'num' for (int i=2; i<=sqrt(num); i++) { // if 'i' is divisor of 'num' if (num%i==0) { // if both divisors are same then add // it only once else add both if (i==(num/i)) result += i; else result += (i + num/i); } } // Add 1 to the result as 1 is also a divisor return (result + 1); } // Driver program to run the case int main() { int num = 36; cout << divSum(num); return 0; }
Java
// JAVA program to find sum of all divisors // of a natural number import java.math.*; class GFG { // Function to calculate sum of all proper // divisors num --> given natural number static int divSum(int num) { // Final result of summation of divisors int result = 0; // find all divisors which divides 'num' for (int i = 2; i <= Math.sqrt(num); i++) { // if 'i' is divisor of 'num' if (num % i == 0) { // if both divisors are same then // add it only once else add both if (i == (num / i)) result += i; else result += (i + num / i); } } // Add 1 to the result as 1 is also // a divisor return (result + 1); } // Driver program to run the case public static void main(String[] args) { int num = 36; System.out.println(divSum(num)); } } /*This code is contributed by Nikita Tiwari*/
Python3
# PYTHON program to find sum of all # divisors of a natural number import math # Function to calculate sum of all proper # divisors num --> given natural number def divSum(num) : # Final result of summation of divisors result = 0 # find all divisors which divides 'num' i = 2 while i<= (math.sqrt(num)) : # if 'i' is divisor of 'num' if (num % i == 0) : # if both divisors are same then # add it only once else add both if (i == (num / i)) : result = result + i; else : result = result + (i + num/i); i = i + 1 # Add 1 to the result as 1 is also # a divisor return (result + 1); # Driver program to run the case num = 36 print (divSum(num)) # This code is contributed by Nikita Tiwari
C#
// C# program to find sum of all // divisorsof a natural number using System; class GFG { // Function to calculate sum of all proper // divisors num --> given natural number static int divSum(int num) { // Final result of summation of divisors int result = 0; // find all divisors which divides 'num' for (int i = 2; i <= Math.Sqrt(num); i++) { // if 'i' is divisor of 'num' if (num % i == 0) { // if both divisors are same then // add it only once else add both if (i == (num / i)) result += i; else result += (i + num / i); } } // Add 1 to the result as 1 // is also a divisor return (result + 1); } // Driver Code public static void Main() { int num = 36; Console.Write(divSum(num)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program to find sum of // all divisors of a natural number // Function to calculate sum of // all proper divisors // num --> given natural number function divSum($num) { // Final result of // summation of divisors $result = 0; // find all divisors // which divides 'num' for ($i = 2; $i <= sqrt($num); $i++) { // if 'i' is divisor of 'num' if ($num % $i == 0) { // if both divisors are // same then add it only // once else add both if ($i == ($num / $i)) $result += $i; else $result += ($i + $num / $i); } } // Add 1 to the result as // 1 is also a divisor return ($result + 1); } // Driver Code $num = 36; echo(divSum($num)); // This code is contributed by Ajit. ?>
Javascript
<script> // Javascript program to find sum of all divisors of // a natural number // Function to calculate sum of all proper divisors // num --> given natural number function divSum(num) { // Final result of summation of divisors let result = 0; // find all divisors which divides 'num' for (let i=2; i<=Math.sqrt(num); i++) { // if 'i' is divisor of 'num' if (num%i==0) { // if both divisors are same then add // it only once else add both if (i==(num/i)) result += i; else result += (i + num/i); } } // Add 1 to the result as 1 is also a divisor return (result + 1); } // Driver program to run the case let num = 36; document.write(divSum(num)); // This code is contributed by Mayank Tyagi </script>
Producción :
55
Complejidad temporal: O(√n)
Espacio auxiliar: O(1)
Consulte la publicación a continuación para obtener una solución y una fórmula optimizadas.
Solución eficiente para la suma de todos los factores de un número
Este artículo es una contribución de Aarti_Rathi y Shashank Mishra (Gullu) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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