Число является совершенным числом, если равно сумме его собственных делителей, то есть сумме его положительных делителей, исключая само число. Напишите функцию, чтобы проверить, является ли данное число идеальным или нет.
Примеры:
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++ program to check if a given number is perfect
// or not
#include<iostream>
using namespace std;
// Returns true if n is perfect
bool isPerfect(long long int n)
{
// To store sum of divisors
long long int sum = 1;
// Find all divisors and add them
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;
}
}
// If sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Driver program
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 program to check if a given
// number is perfect or not
class GFG
{
// Returns true if n is perfect
static boolean isPerfect(int n)
{
// To store sum of divisors
int sum = 1;
// Find all divisors and add them
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;
}
}
// If sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Driver program
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");
}
}
// This code is contributed by mits
# Python3 code to check if a given
# number is perfect or not
# Returns true if n is perfect
def isPerfect( n ):
# To store sum of divisors
sum = 1
# Find all divisors and add them
i = 2
while i * i <= n:
if n % i == 0:
sum = sum + i + n/i
i += 1
# If sum of divisors is equal to
# n, then n is a perfect number
return (True if sum == n and n!=1 else False)
# Driver program
print("Below are all perfect numbers till 10000")
n = 2
for n in range (10000):
if isPerfect (n):
print(n , " is a perfect number")
# This code is contributed by "Sharad_Bhardwaj".
// C# program to check if a given
// number is perfect or not
class GFG
{
// Returns true if n is perfect
static bool isPerfect(int n)
{
// To store sum of divisors
int sum = 1;
// Find all divisors and add them
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;
}
}
// If sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Driver program
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");
}
}
// This code is contributed by chandan_jnu
<?php
// PHP program to check if a given number
// is perfect or not
// Returns true if n is perfect
function isPerfect($n)
{
// To store sum of divisors
$sum = 1;
// Find all divisors and add them
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;
}
}
// If sum of divisors is equal to
// n, then n is a perfect number
if ($sum == $n && $n != 1)
return true;
return false;
}
// Driver Code
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";
// This code is contributed by mits
?>
<script>
// Javascript program to check if a given number is perfect
// or not
// Returns true if n is perfect
function isPerfect(n)
{
// To store sum of divisors
sum = 1;
// Find all divisors and add them
for (let i=2; i*i<=n; i++)
{
if (n%i==0)
{
if(i*i!=n)
sum = sum + i + n/i;
else
sum=sum+i;
}
}
// If sum of divisors is equal to
// n, then n is a perfect number
if (sum == n && n != 1)
return true;
return false;
}
// Driver program
document.write("Below are all perfect numbers till 10000" + "<br>");
for (let n =2; n<10000; n++)
if (isPerfect(n))
document.write(n + " is a perfect number" + "<br>");
// This code is contributed by Mayank Tyagi
</script>
Выход:
Below are all perfect numbers till 10000
6 is a perfect number
28 is a perfect number
496 is a perfect number
8128 is a perfect numberВременная Сложность: √n
Ниже приведены некоторые интересные факты об идеальных числах:
1) Каждое четное совершенное число имеет вид 2p?1(2p ? 1) где 2p ? 1-простое число.
2) Неизвестно, существуют ли какие-либо нечетные совершенные числа.
