1、什么是完全数
完全数(Perfect number)是一些特殊的自然整数。完全数等于其所有因子的和。这里所谓的因子是指所有可以整除这个数的数,而不包括该数本身。
完全数的基本规则和性质,以及判断完全数的算法。
其实谈到完全数,与之相关的两个概念便是亏数和盈数。
一般来说,通过其所有真因子的和来判断一个自然数是亏数、盈数及完全数。
・当一个自然数的所有真因子的和小于该自然数,那么该自然数便是亏数;
・当一个自然数的所有真因子的和大于该自然数,那么该自然数便是盈数;
・当一个自然数的所有真因子的和等于该自然数,那么该自然数便是完全数。
例如,4的所有真因子包括1和2,而4>1+2,所以4是一个亏数;6的所有真因子包括1、2、3,而6=1+2+3,因此6是一个完全数;12的所有真因子包括1、2、3、4、6,而12<1+2+3+4+6,所以12是一个盈数。
下面举几个典型的完全数的例子:
6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248
8128=1+2+4+8+16+32+64+127+254+508+1016+2032+4064
2、完全数的性质
对于完全数的研究,可以追溯到公元前6世纪。当时,毕达哥拉斯已经发现6和28是完全数。到目前为止,总共找到47个完全数。而寻找完全数是比较困难的,完全数的值越来越大,有时候需要借助高速的计算机来寻找。在所有的自然数中总共有多少个完全数,至今仍然是个谜,许多数学家在为之奋斗。另外,奇特的是,目前所有发现的完全数都是偶数,到底是否存在奇数的完全数也是一个谜。
1)每一个完全数都可以表示成连续自然数的和
每一个完全数都可以表示成连续自然数的和,这些自然数并不一定是完全数的因数。
例如:6=1+2+3
28=1+2+3+4+5+6+7
496=1+2+3+4+…+29+30+31
2)每一个完全数都是调和数
如果一个正整数的所有因子的调和平均是整数,那么这个正整数便是调和数。而每一个完全数都是调和数,例如:
对于完全数6来说,1/1+1/2+1/3+1/6=2
对于完全数28来说,1/1+1/2+1/4+1/7+1/14+1/28=2
3)每一个完全数都可以表示为2的一些连续正整数次幂之和
每一个完全数都可以表示为2的一些连续正整数次幂之和,例如:
6=2^1+2^2
28=2^2+2^3+2^4
8128=2^6+2^7+2^8+2^9+2^10+2^11+2^12
4)已知的完全数都是以6或者8结尾
已知的完全数都是以6或者8结尾,例如,6、28、496、8128、33550336等。从这里也可以看出,已知的每一个完全数都是偶数,但还没有严格证明没有奇数的完全数。
5)除6之外的完全数都可以表示成连续奇立方之和
除6之外的完全数都可以表示成连续奇立方之和,例如:
28=1^3+3^3
496=1^3+3^3+5^3+7^3
8128=1^3+3^3+5^3+…+15^3
3、计算完全数算法
一个简单的解决方案是遍历从1到n-1的每个数字,并检查它是否是除数。保持所有除数之和。如果 sum 等于 n,则返回 true,否则返回 false。
一个有效的解决方案是遍历数字直到n的平方根。如果一个数字“i”除以n,则将“i”和 n/i 加起来。
(1)c++
// 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;
}
(2)Java
//检查给定数字是否完美的Java程序
class WQS
{
// 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");
}
}
(3)C#
class WQS
{
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");
}
}
(4)Python
# 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")
(5)PHP
<?php
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";
?>
(6)Javascript
<script>
function isPerfect(n)
{
// 存储除数之和
sum = 1;
// 找到所有除数并求和
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;
}
}
// 如果除数之和等于n,则n是完美数
if (sum == n && n != 1)
return true;
return false;
}
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>");
</script>
今天的文章数据结构中的完全图_RSA算法的安全性建立在数论中分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/83562.html