Se dice que un número n es un número deficiente si la suma de todos los divisores del número indicado por divisorsSum(n) es menor que el doble del valor del número n. Y la diferencia entre estos dos valores se llama deficiencia .
Matemáticamente, si la condición siguiente se mantiene, se dice que el número es Deficiente:
divisorsSum(n) < 2 * n deficiency = (2 * n) - divisorsSum(n)
Los primeros Números Deficientes son:
1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19…..
Dado un número n, nuestra tarea es encontrar si este número es número deficiente o no.
Ejemplos:
Input: 21 Output: YES Divisors are 1, 3, 7 and 21. Sum of divisors is 32. This sum is less than 2*21 or 42. Input: 12 Output: NO Input: 17 Output: YES
Una solución simple es iterar todos los números del 1 al n y verificar si el número divide n y calcular la suma. Compruebe si esta suma es menor que 2 * n o no.
Tiempo Complejidad de este enfoque: O ( n )
Solución Optimizada:
Si observamos cuidadosamente, los divisores del número n están presentes en pares. Por ejemplo, si n = 100, entonces todos los pares de divisores son: (1, 100), (2, 50), (4, 25), (5, 20), (10, 10)
Usando este hecho podemos acelerar nuestro programa.
Al comprobar los divisores tendremos que tener cuidado si hay dos divisores iguales como en el caso de (10, 10). En tal caso tomaremos solamente uno de ellos en el cálculo de la suma.
Implementación del enfoque optimizado
C++
// C++ program to implement an Optimized Solution // to check Deficient Number #include <bits/stdc++.h> using namespace std; // Function to calculate sum of divisors int divisorsSum(int n) { int sum = 0; // Initialize sum of prime factors // Note that this loop runs till square root of n for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, take only one // of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } return sum; } // Function to check Deficient Number bool isDeficient(int n) { // Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)); } /* Driver program to test above function */ int main() { isDeficient(12) ? cout << "YES\n" : cout << "NO\n"; isDeficient(15) ? cout << "YES\n" : cout << "NO\n"; return 0; }
Java
// Java program to check Deficient Number import java.io.*; class GFG { // Function to calculate sum of divisors static int divisorsSum(int n) { int sum = 0; // Initialize sum of prime factors // Note that this loop runs till square root of n for (int i = 1; i <= (Math.sqrt(n)); i++) { if (n % i == 0) { // If divisors are equal, take only one // of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } return sum; } // Function to check Deficient Number static boolean isDeficient(int n) { // Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)); } /* Driver program to test above function */ public static void main(String args[]) { if (isDeficient(12)) System.out.println("YES"); else System.out.println("NO"); if (isDeficient(15)) System.out.println("YES"); else System.out.println("NO"); } } // This code is contributed by Nikita Tiwari
Python3
# Python program to implement an Optimized # Solution to check Deficient Number import math # Function to calculate sum of divisors def divisorsSum(n) : sum = 0 # Initialize sum of prime factors # Note that this loop runs till square # root of n i = 1 while i<= math.sqrt(n) : if (n % i == 0) : # If divisors are equal, take only one # of them if (n // i == i) : sum = sum + i else : # Otherwise take both sum = sum + i; sum = sum + (n // i) i = i + 1 return sum # Function to check Deficient Number def isDeficient(n) : # Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)) # Driver program to test above function if ( isDeficient(12) ): print ("YES") else : print ("NO") if ( isDeficient(15) ) : print ("YES") else : print ("NO") # This Code is contributed by Nikita Tiwari
C#
// C# program to implement an Optimized Solution // to check Deficient Number using System; class GFG { // Function to calculate sum of // divisors static int divisorsSum(int n) { // Initialize sum of prime factors int sum = 0; // Note that this loop runs till // square root of n for (int i = 1; i <= (Math.Sqrt(n)); i++) { if (n % i == 0) { // If divisors are equal, // take only one of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } return sum; } // Function to check Deficient Number static bool isDeficient(int n) { // Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)); } /* Driver program to test above function */ public static void Main() { string var = isDeficient(12) ? "YES" : "NO"; Console.WriteLine(var); string var1 = isDeficient(15) ? "YES" : "NO"; Console.WriteLine(var1); } } // This code is contributed by vt_m
PHP
<?php // PHP program to implement // an Optimized Solution // to check Deficient Number // Function to calculate // sum of divisors function divisorsSum($n) { // Initialize sum of // prime factors $sum = 0; // Note that this loop runs // till square root of n for ($i = 1; $i <= sqrt($n); $i++) { if ($n % $i==0) { // If divisors are equal, // take only one of them if ($n / $i == $i) { $sum = $sum + $i; } // Otherwise take both else { $sum = $sum + $i; $sum = $sum + ($n / $i); } } } return $sum; } // Function to check // Deficient Number function isDeficient($n) { // Check if sum(n) < 2 * n return (divisorsSum($n) < (2 * $n)); } // Driver Code $ds = isDeficient(12) ? "YES\n" : "NO\n"; echo($ds); $ds = isDeficient(15) ? "YES\n" : "NO\n"; echo($ds); // This code is contributed by ajit;. ?>
Javascript
<script> // Javascript program to check Deficient Number // Function to calculate sum of divisors function divisorsSum(n) { let sum = 0; // Initialize sum of prime factors // Note that this loop runs till square root of n for (let i = 1; i <= (Math.sqrt(n)); i++) { if (n % i == 0) { // If divisors are equal, take only one // of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } return sum; } // Function to check Deficient Number function isDeficient(n) { // Check if sum(n) < 2 * n return (divisorsSum(n) < (2 * n)); } // Driver code to test above methods if (isDeficient(12)) document.write("YES" + "<br/>"); else document.write("NO" + "<br/>"); if (isDeficient(15)) document.write("YES" + "<br/>"); else document.write("NO" + "<br/>"); // This code is contributed by avijitmondal1998. </script>
Producción :
NO YES
Complejidad de tiempo: O (sqrt (n))
Espacio auxiliar: O (1)
Referencias:
https://en.wikipedia.org/wiki/Deficient_number
Este artículo es una contribución de Harsh Agarwal . 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