亲宝软件园·资讯

展开

Python实现完全数的示例详解

¿¿¿¡¡¡ 人气:0

一、前言

卷起来好吧,元旦已经过了,就开始写文章模式了。

这篇文章会对完全数的各种侦测进行详细解释。写作不易,支持一波~

二、完全数是什么

1、定义

老规矩,先来了解完全数是什么。

完全数,又称完美数,定义为:这个数的所有因数(不包括这个数本身)加起来刚好等于这个数。比如6就是完全数,因为6的因数有1,2,3(不包括6本身),1+2+3正好等于6。

所以如果有人给你扣6,那说明他在夸赞你十分完美(bushi。

完全数是一个叫毕达哥拉斯的提出来的,被誉为“最古老的数学问题”,这人还提出了我们熟悉的勾股定理和黄金比例。

目前一共找到了51个完全数,非常的稀有,比较小的有6、28、496、8128、33550336等等。

目前还没有人找到奇数完全数,也没有人能证明“没有奇数完全数”。但是,一个叫做奥斯丁·欧尔的人证明出来:要是有奇完全数,必须能表示成12x质数+1或者36x质数+9,并且在10^300以内没有奇完全数的存在。

完全数会越来越大,第39个完全数有25674127位数,如果用四号字字体打印出来,也能变成一本字典。

2、规律

这些数之间有没有一些规律呢?

有,并且很多。(以下规律仅仅是目前发现的完全数都符合这个定律,部分未证明)

第一,完全数都是以6或28结尾的。

第二,完全数都是三角形数,例如6可以表示成1+2+3,28可以表示成1+2+3+4+5+6+7。

第三,除了6以外都可以表示成连续隔2奇立方数之和。例如28表示成1^3+3^3,496表示成1^3+3^3+5^3+7^3。

第四,完全数的所有因数的倒数的和为2。例如6所有因数的倒数是1,1/2,1/3,1/6,相加为2。28所有因数的倒数是1,1/2,1/4,1/7,1/14,1/28,相加为2。

第五,完全数都可以表示成2的连续数次方之和。例如6可以表示成2^1+2^2,28可以表示成2^2+2^3+2^4。

第六,6以外的完全数经过碾转之后为1。碾转就是把他的各个位数相加一直到只剩一位数。例如28碾转数为:2+8=10,1+0=1。496碾转数为:4+9+6=19,1+9=10,1+0=1。

第七,6以外的完全数除以9一定余数为1。例如:28除以9=3…1,496除以9=55…1。

知道为啥有一个别名叫完美数了吧?太完美了!

3、梅森素数

之后又冒出来了一个梅森素数,这是欧几里得整出来的。我们定义P是一个质数,如果2^p-1也是质数,那么这个质数就是“梅森素数”。

知道梅森素数之后,把P带入公式2^(p-1)(2^p-1),咔咔一顿算,结果就是完全数。

我们想想是不是这样。

因为2是质数,2^2-1是3也是质数,那么3就是梅森素数。把2带入公式,咔咔一顿算结果就是6。

3是质数,2^3-1是7也是质数,那么7就是梅森素数。把3带入公式,咔咔一顿算结果就是28。

欧拉证明出来,所有完全数都符合这个形式。有了这个公式计算就更简便了。

三、版本(1.0):硬算

接下来,我们先写程序硬算一遍。

我们需要让程序找到一个数的每一个除了本身之外的因数,还要把它们都加起来,这些程序可以放在一个函数里面。之后再套上循环,数自增重复调用就行了。是不是很简单?

先完成找数的所有因数的效果。

我们要创建一个函数,用for循环和range套上要寻找的数字,如果这个数是要寻找的数字的因数,就用一个变量自增。检测结束后检测因数和要寻找的数字是否相等,返回真或假。

def find(find_number):#新建函数find查找因数并进行判断
    he=0#初始化变量
    for i in range(1,find_number):#循环find_number次
        if find_number%i==0:#如果i是find_number的因数
            he=he+i#赋值
    #这时候,he就是find_number所有因数的和了
    if he==find_number:#比较
        return True
    else:
        return False

最关键的部分已经做好了,补全代码你可以自己试试~

补全代码,先询问要检测到哪里,之后while循环或者for+range来计数,调用函数获取信息,十分的简单。

完整程序就是这样:

def find(find_number):#新建函数find查找因数并进行判断
    he=0#初始化变量
    for i in range(1,find_number):#循环find_number次
        if find_number%i==0:#如果i是find_number的因数
            he=he+i
    #这时候,he就是find_number所有因数的和了
    if he==find_number:#比较
        return True
    else:
        return False
a=int(input("输入要检测1到多少位的完全数"))
for i in range(1,a+1):
    if find(i):
        print(i,"是完全数")

四、版本1.1:数的末尾侦测

从上文我们可以知道,完全数的末尾都是6或者28,这样的话,我们就又能节约一下运行时间了。

有人问了:诶诶诶,怎么知道一个整数的末尾是多少呢?

很简单,变成字符串再截取就行了。

def find(find_number):#新建函数find查找因数并进行判断
    he=0#初始化变量
    for i in range(1,find_number):#循环find_number次
        if find_number%i==0:#如果i是find_number的因数
            he=he+i
    #这时候,he就是find_number所有因数的和了
    if he==find_number:#比较
        return True
    else:
        return False
a=int(input("输入要检测1到多少位的完全数"))
for i in range(1,a+1):
    if str(i)[-1]=='6' or str(i)[-1]=='8':
        if find(i):
            print(i,"是完全数")

这样运行速度直接快了一倍好吧。

五、版本1.2:除以9侦测

完全数除以9都余1,我们也可用这一点来加快运行速度。不过,千万不要忽略“排除6”,再加一个是不是6的侦测。看起来更烦琐了,但是这样做将近能快3倍速度。

def find(find_number):#新建函数find查找因数并进行判断
    he=0#初始化变量
    for i in range(1,find_number):#循环find_number次
        if find_number%i==0:#如果i是find_number的因数
            he=he+i
    #这时候,he就是find_number所有因数的和了
    if he==find_number:#比较
        return True
    else:
        return False
a=int(input("输入要检测1到多少位的完全数"))
for i in range(1,a+1):
    if str(i)[-1]=='6' or str(i)[-1]=='8':
        if i%9==1 or i==6:
            if find(i):
                print(i,"是完全数")

六、版本2.0:梅森素数侦测

这是最后的终极方法,就是寻找梅森素数。

首先还是要侦测素数的大循环,if来判断素数是不是梅森素数,是的话就代入公式输出,十分的简单。

在上一个哥德巴 赫猜想的文章里面已经有了素数侦测的函数,这里直接拿过来用,诶嘿。

c,运行太快了,停不住了,诶!

(哔~)

我们再加一个等待时间就好了,有点快了。

from time import sleep
zhishu=[]#储存质数的列表
for i in range(2,10000):#循环检测质数
    for j in range(2,i-1):#2到i内的每一个数
        if i%j==0:#如果i不是质数
            break#退出循环
    else:#如果正常结束循环就是i是质数
        zhishu.append(i)#zhishu添加i
 
for shu in zhishu:
    if 2**shu-1 in zhishu:
        print(2**(shu-1)*(2**shu-1),"是完全数")
        sleep(1)

但是这样检测有一个致命的缺点——只能检测10000以内的,因为我们用的是in来判断2**shu-1是不是质数,大于10000就没有了,要是能有一个质数表数据的话,肯定能找他十几个。

加载全部内容

相关教程
猜你喜欢
用户评论