Número deficiente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *