Рубрики

Номер дефекта

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

Математически, если условие выполнено ниже, число называется Дефицит:

divisorsSum(n) < 2 * n
deficiency = (2 * n) - divisorsSum(n)

Первые несколько номеров дефектов:

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19… ..

Учитывая число n, наша задача состоит в том, чтобы определить, является ли этот номер номером дефекта или нет.

Примеры :

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

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

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

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

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

Реализация оптимизированного подхода

C ++

// C ++ программа для реализации оптимизированного решения
// проверить номер дефекта
#include <bits/stdc++.h>

using namespace std;

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

int divisorsSum(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);

            }

        }

    }

    return sum;

}

  
// Функция для проверки номера дефекта

bool isDeficient(int n)

{

    // Проверяем, если sum (n) <2 * n

    return (divisorsSum(n) < (2 * n));

}

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

int main()

{

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

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

    return 0;

}

Джава

// Java-программа для проверки номера дефекта

  

import java.io.*;

  

class GFG {

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

    static int divisorsSum(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);

                }

            }

        }

  

        return sum;

    }

  

    // Функция для проверки номера дефекта

    static boolean isDeficient(int n)

    {

        // Проверяем, если sum (n) <2 * n

        return (divisorsSum(n) < (2 * n));

    }

  

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

    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");

    }

}

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

питон

# Python программа для реализации Оптимизированного
# Решение для проверки номера дефекта

import math

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

def divisorsSum(n) :

    sum = 0  # Инициализировать сумму простых факторов

  

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

    # корень из n

    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

    return sum

    
# Функция для проверки номера дефекта

def isDeficient(n) :

  

    # Проверьте, если сумма (n) <2 * n

    return (divisorsSum(n) < (2 * n))

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

if ( isDeficient(12) ):

    print "YES"

else :

    print "NO"

if ( isDeficient(15) ) :

    print "YES"

else

    print "NO"

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

C #

// C # программа для реализации оптимизированного решения
// проверить номер дефекта

using System;

  

class GFG {

  

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

    // делители

    static int divisorsSum(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);

                }

            }

        }

  

        return sum;

    }

  

    // Функция для проверки номера дефекта

    static bool isDeficient(int n)

    {

  

        // Проверяем, если sum (n) <2 * n

        return (divisorsSum(n) < (2 * n));

    }

  

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

    public static void Main()

    {

        string var = isDeficient(12) ? "YES" : "NO";

        Console.WriteLine(var);

  

        string var1 = isDeficient(15) ? "YES" : "NO";

        Console.WriteLine(var1);

    }

}

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

PHP

<?php
// PHP-программа для реализации
// Оптимизированное решение
// проверить номер дефекта

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

function divisorsSum($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);

            }

        }

    }

    return $sum;

}

  
// Функция для проверки
// Номер дефекта

function isDeficient($n)

{

    // Проверяем, если sum (n) <2 * n

    return (divisorsSum($n) < (2 * $n));

}

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

$ds = isDeficient(12) ? 

              "YES\n"

                "NO\n";

    echo($ds);

$ds = isDeficient(15) ? 

              "YES\n"

                "NO\n";

    echo($ds);

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


Выход :

NO
YES

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

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

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

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

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

Номер дефекта

0.00 (0%) 0 votes