Рубрики

Идеальный номер

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

Примеры:

Input: n = 15
Output: false
Divisors of 15 are 1, 3 and 5. Sum of 
divisors is 9 which is not equal to 15.

Input: n = 6
Output: true
Divisors of 6 are 1, 2 and 3. Sum of 
divisors is 6.

Простое решение — просмотреть каждое число от 1 до n-1 и проверить, является ли оно делителем. Поддерживать сумму всех делителей. Если сумма становится равной n, вернуть true, иначе вернуть false.

Эффективное решение — пройти через числа до квадратного корня из n. Если число «i» делит n, то к сумме добавляются «i» и n / i.

Ниже приведена реализация эффективного решения.

C ++

// C ++ программа для проверки, является ли данное число идеальным
// или не
#include<iostream>

using namespace std;

  
// Возвращает true, если n идеально

bool isPerfect(long long int n)

{

    // Хранить сумму делителей

    long long int sum = 1;

   

    // Найти все делители и добавить их

    for (long long int i=2; i*i<=n; i++)

    {

        if (n%i==0)

        {

            if(i*i!=n)

                sum = sum + i + n/i;

            else

                sum=sum+i;

        }

    

     // Если сумма делителей равна

     // n, тогда n идеальное число

     if (sum == n && n != 1)

          return true;

   

     return false;

}

   
// Драйвер программы

int main()

{

    cout << "Below are all perfect numbers till 10000\n";

    for (int n =2; n<10000; n++)

        if (isPerfect(n))

            cout << n << " is a perfect number\n";

   

    return 0;

}

Джава

// Java-программа для проверки, если данный
// номер совершенен или нет

class GFG

{

      
// Возвращает true, если n идеально

static boolean isPerfect(int n)

{

    // Хранить сумму делителей

    int sum = 1;

  

    // Найти все делители и добавить их

    for (int i = 2; i * i <= n; i++)

    {

        if (n % i==0)

        {

            if(i * i != n)

                sum = sum + i + n / i;

            else

                sum = sum + i;

        }

    

    // Если сумма делителей равна

    // n, тогда n идеальное число

    if (sum == n && n != 1)

        return true;

  

    return false;

}

  
// Драйвер программы

public static void main (String[] args)

{

    System.out.println("Below are all perfect"

                                "numbers till 10000");

    for (int n = 2; n < 10000; n++)

        if (isPerfect(n))

            System.out.println( n + 

                    " is a perfect number");

}
}

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

python3

# Python3 код для проверки, если данный
# номер идеален или нет

  
# Возвращает true, если n идеально

def isPerfect( n ):

      

    # Хранить сумму делителей

    sum = 1

      

    # Найти все делители и добавить их

    i = 2

    while i * i <= n:

        if n % i == 0:

            sum = sum + i + n/i

        i += 1

      

    # Если сумма делителей равна

    # n, тогда n идеальное число

      

    return (True if sum == n and n!=1 else False)

  
# Драйверная программа

print("Below are all perfect numbers till 10000")

n = 2

for n in range (10000):

    if isPerfect (n):

        print(n , " is a perfect number")

          
# Этот код предоставлен "Sharad_Bhardwaj".

C #

// C # программа для проверки, если данный
// номер совершенен или нет

  

class GFG

{

      
// Возвращает true, если n идеально

static bool isPerfect(int n)

{

    // Хранить сумму делителей

    int sum = 1;

  

    // Найти все делители и добавить их

    for (int i = 2; i * i <= n; i++)

    {

        if (n % i==0)

        {

            if(i * i != n)

                sum = sum + i + n / i;

            else

                sum = sum + i;

        }

    

    // Если сумма делителей равна

    // n, тогда n идеальное число

    if (sum == n && n != 1)

        return true;

  

    return false;

}

  
// Драйвер программы

static void Main()

{

    System.Console.WriteLine("Below are all perfect"

                                "numbers till 10000");

    for (int n = 2; n < 10000; n++)

        if (isPerfect(n))

            System.Console.WriteLine( n + 

                    " is a perfect number");

}
}

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

PHP

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

  
// Возвращает true, если n идеально

function isPerfect($n)

{

    // Хранить сумму делителей

    $sum = 1;

  

    // Найти все делители и добавить их

    for ($i = 2; $i * $i <= $n; $i++)

    {

        if ($n % $i == 0)

        {

            if($i * $i != $n)

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

            else

                $sum = $sum + $i;

        }

    

    // Если сумма делителей равна

    // n, тогда n идеальное число

    if ($sum == $n && $n != 1)

        return true;

  

    return false;

}

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

echo "Below are all perfect numbers till 10000\n";

for ($n = 2; $n < 10000; $n++)

    if (isPerfect($n))

        echo "$n is a perfect number\n";

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


Выход:

Below are all perfect numbers til 10000
6 is a perfect number
28 is a perfect number
496 is a perfect number
8128 is a perfect number

Сложность времени: √n

Ниже приведены некоторые интересные факты о совершенных номерах:
1) Каждое четное совершенное число имеет вид 2 ? 1 (2 ? 1) где 2 ? 1 простое.
2) Неизвестно, существуют ли какие-либо нечетные совершенные числа.


Ссылки:

https://en.wikipedia.org/wiki/Perfect_number

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

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

Идеальный номер

0.00 (0%) 0 votes