Рубрики

Обильное количество

Число n называется Abundant Number, если сумма всех правильных делителей числа, обозначенного sum (n), больше, чем значение числа n. И разница между этими двумя значениями называется изобилием .
Математически, если условие выполнено ниже, число называется Обильным числом:

sum(n)> n
abundance =  sum(n) - n
sum(n): aliquot sum - The sum of all proper divisors of n

Учитывая число n, наша задача состоит в том, чтобы найти, является ли это число Обильным числом или нет.

Первые несколько чисел: 12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66… ..

Примеры :

Input: 21
Output: NO

Input: 12
Output: YES

Input: 17
Output: NO

Способ 1

Простое решение состоит в том, чтобы перебрать все числа от 1 до n-1 и проверить, делит ли число n, и вычислить сумму. Проверьте, больше ли эта сумма, чем n, или нет.

Сложность времени этого подхода: O (n)

Оптимизированное решение:

Если мы внимательно наблюдаем, делители числа n присутствуют в парах. Например, если n = 100, то все пары делителей: (1 100), (2,50), (4,25), (5,20), (10,10)

Используя этот факт, мы можем ускорить нашу программу. При проверке делителей мы должны быть осторожны, если есть два равных делителя, как в случае (10, 10). В таком случае мы возьмем только один из них при расчете суммы.
Вычтите число n из суммы всех делителей, чтобы получить сумму правильных делителей.

C ++

// Оптимизированное решение для проверки численности
#include <bits/stdc++.h>

using namespace std;

  
// Функция для вычисления суммы делителей

int getSum(int n)

{

    int sum = 0;

  

    // Обратите внимание, что этот цикл работает до квадратного корня

    // из n

    for (int i=1; i<=sqrt(n); i++)

    {

        if (n%i==0)

        {

            // Если делители равны, взять только один

            // их

            if (n/i == i)

                sum = sum + i;

  

            else // В противном случае взять оба

            {

                sum = sum + i;

                sum = sum + (n / i);

            }

        }

    }

  

    // вычисляем сумму только всех правильных делителей

    sum = sum - n;

    return sum;

}

  
// Функция для проверки численности

bool checkAbundant(int n)

{

    // Возвращаем true, если сумма делителей больше

    // чем п.

    return (getSum(n) > n);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    checkAbundant(12)? cout << "YES\n" : cout << "NO\n";

    checkAbundant(15)? cout << "YES\n" : cout << "NO\n";

    return 0;

}

Джава

// Оптимизированное решение для проверки численности
// в ЯВА

import java.io.*; 

import java.math.*;

  
// Функция для вычисления суммы делителей

class GFG{

    static int getSum(int n)

    {

        int sum = 0;

    

       // Обратите внимание, что этот цикл работает до квадрата

       // корень n

        for (int i=1; i<=(Math.sqrt(n)); i++)

        {

            if (n%i==0)

            {

             // Если делители равны, берут только

             // один из них

                if (n/i == i)

                   sum = sum + i;

    

                else // В противном случае взять оба

                {

                   sum = sum + i;

                   sum = sum + (n / i);

                }

            }

        }

    

        // вычисляем сумму всех правильных делителей

       // только

        sum = sum - n;

        return sum;

    }

    

    // Функция для проверки численности

    static boolean checkAbundant(int n)

    {

      // Возвращаем true, если сумма делителей равна

      // больше чем n.

      return (getSum(n) > n);

    }

    

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[])throws 

                                   IOException

    {

      if(checkAbundant(12))

          System.out.println("YES");

      else

          System.out.println("NO");

      if(checkAbundant(15))

          System.out.println("YES");

      else

          System.out.println("NO");

    }

}

   
// Этот код предоставлен Никитой Тивари.

питон

# Оптимизированное решение для проверки численности
# в питоне

import math

  
# Функция для вычисления суммы делителей

def getSum(n) :

    sum = 0

      

    # Обратите внимание, что этот цикл работает до квадратного корня

    № из п

    i = 1

    while i <= (math.sqrt(n)) :

        if n%i == 0 :

              

        # Если делители равны, возьмите только один

        # их

            if n/i == i :

                sum = sum + i

            else : # В противном случае возьмите оба

                sum = sum + i

                sum = sum + (n / i )

        i = i + 1

      

    # вычислить сумму только всех правильных делителей

    sum = sum - n

    return sum

  
# Функция для проверки численности

def checkAbundant(n) :

      

    # Вернуть true, если сумма делителей больше

    # чем n.

    if (getSum(n) > n) :

        return 1

    else :

        return 0

          
# Программа драйвера для проверки вышеуказанной функции * /

if(checkAbundant(12) == 1) :

    print "YES"

else :

    print "NO"

      

if(checkAbundant(15) == 1) :

    print "YES"

else :

    print "NO"

      
# Этот код предоставлен Никитой Тивари.

C #

// Оптимизированное решение для проверки численности
// в C #
// Функция для вычисления суммы делителей

using System;

  

class GFG {

      

    // Функция для вычисления суммы делителей

    static int getSum(int n)

    {

        int sum = 0;

  

        // Обратите внимание, что этот цикл работает до квадрата

        // корень n

        for (int i = 1; i <= (Math.Sqrt(n)); i++) {

            if (n % i == 0) {

                  

                // Если делители равны, берут только

                // один из них

                if (n / i == i)

                    sum = sum + i;

  

                else // В противном случае взять оба

                {

                    sum = sum + i;

                    sum = sum + (n / i);

                }

            }

        }

  

        // вычисляем сумму всех правильных делителей

        // только

        sum = sum - n;

        return sum;

    }

  

    // Функция для проверки численности

    static bool checkAbundant(int n)

    {

          

        // Возвращаем true, если сумма делителей равна

        // больше чем n.

        return (getSum(n) > n);

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void Main()

    {

        if (checkAbundant(12))

            Console.WriteLine("YES");

        else

            Console.WriteLine("NO");

              

        if (checkAbundant(15))

            Console.WriteLine("YES");

        else

            Console.WriteLine("NO");

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для Оптимизированного
// решение для проверки численности

  
// Функция для расчета
// сумма делителей

function getSum($n)

{

    $sum = 0;

  

    // Обратите внимание, что этот цикл выполняется

    // до квадратного корня из n

    for ($i = 1; $i <= sqrt($n); $i++)

    {

        if ($n % $i == 0)

        {

            // Если делители равны, возьмите

            // только один из них

            if ($n / $i == $i)

                $sum = $sum + $i;

  

            // В противном случае взять оба

            else 

            {

                $sum = $sum + $i;

                $sum = $sum + ($n / $i);

            }

        }

    }

  

    // вычисляем сумму всего

    // только правильные делители

    $sum = $sum - $n;

    return $sum;

}

  
// Функция для проверки численности

function checkAbundant($n)

{

    // Возвращаем true если сумма

    // делители больше чем n.

    return (getSum($n) > $n);

}

  
// Код драйвера

$k = checkAbundant(12) ? "YES\n" : "NO\n";

echo($k);

  

$k = checkAbundant(15) ? "YES\n" : "NO\n";

echo($k);

  
// Этот код предоставлен Ajit.
?>


Выход :

YES
NO

Сложность времени: O (sqrt (n))
Вспомогательное пространство: O (1)

Ссылки:
https://en.wikipedia.org/wiki/Abundant_number

Эта статья предоставлена Суровым Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

-Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме ».

Рекомендуемые посты:

Обильное количество

0.00 (0%) 0 votes