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