dingsir的个人博客分享 http://blog.sciencenet.cn/u/dingsir

博文

python小程序,验证2的67次方减1不是质数

已有 2786 次阅读 2022-6-14 23:03 |个人分类:其它兴趣|系统分类:科研笔记

晚上看书时,有个小故事吸引了我,1903年,哥伦比亚大学的柯尔发表了一个无言的演讲,内容如下:

书本的介绍.jpg


柯尔为了得到这个结果,计算了20年。在计算机普及的今天,我们验算这个结果要用多少时间呢?我想了想,写了一小段python代码来试算一下,代码如下:

#验证2^67-1 是合数且得出其因子。
#因为只有尾数是1,3,7,9的数才可能是尾数为7的数字的因子,因此其它尾数可以跳过。
#(其实,10以上的质数,其个位也只能是1,3,7,9这4种)

# 先求出大数的平方根的整数部分,其因子之一必不比此(整数部分+1)大,因此循环可以少很多
import math
import datetime
BigN=2**67-1
Root=round(math.sqrt(BigN))+1
littleFactor=round(Root / 10)+1
startT=datetime.datetime.now()
for i in range(littleFactor):
   a=i*10+1
   b=i*10+3
   c=i*10+7
   d=i*10+9
   #去掉下面显示进度的这一句,时间可以缩短到41秒。
   #if (i%10000==0): print(i)
   if (BigN % a)==0 and (a!=1):
       print (a, ", ", BigN/a, "is its factor!")
       break
   if(BigN % b)==0:
       print(b, ", ", BigN/b,"is its factor!")
       break
   if (BigN %c)==0:
       print(c,", ", BigN /c, "is its factor!")
       break
   if(BigN %d)==0:
       print(d, ", ", BigN /d, "is its factor!")
       break
endT=datetime.datetime.now()
print("运行时间是:", endT-startT)  
   

在我的笔记本上测试,如果显示进度,速度慢一点,结果是

运行时间1.png

如果屏蔽显示进度的那一句,结果是

运行时间2.png

很显然这个代码还没有好好优化,应该还有大的优化空间。

现在一分钟不到就计算出结果。

科学技术是生产力,真不是空话。


BTW,如果想知道1992年时最大的梅森素数2^756839 -1有多大,也可以在Python命令行试一下,2**756839-1, 结果真的很长!然而,2019年发现的第51个梅森素数M82589933更是恐怖,它就是2**82589933 -1.



https://blog.sciencenet.cn/blog-1213210-1343008.html

上一篇:Typora更新1.3.6,增加了正则表达式查找和替换
下一篇:图解用SPIRE.XLS 写Excel文件
收藏 IP: 210.13.108.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-29 07:49

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部