当前位置: 首页 > 后端技术 > Python

Python破解谷歌高速公路招聘广告:{无理数e中的前十个连续素数}.com

时间:2023-03-26 16:13:37 Python

一次偶然的机会,在吴军老师的《浪潮之巅(第四版)》看到了这样一个故事。谷歌曾在加州101高速公路的大广告牌上做广告:{无理数中前十位连续素数e}.com知道答案(7427466391.com)的可以通过上述网址输入谷歌的工作地点。而要能够计算出这道题,你必须非常聪明。“很聪明”?吴军老师的话很有意思,我也借助电脑的力量琢磨这道证明题。大家都知道e是一个无理数,换句话说,是一个无穷大的不循环小数。世界上总有一些数学爱好者总是乐于用计算机计算这些无理数的小数位数,π就是这样,e也不例外。所以,第一步是在一些权威的数学网站上找到e的小数位数据;这时候,就是谷歌大法了。来到e的维基百科页面,注意到下面的“A001113”超链接,有什么奇怪的,点进去看看。然后就到了这个OEIS网站的A001113页面,原来是个很权威的数论数据库网站。我以寻宝者的眼光上下左右扫视网页,终于找到了目标。LINKS的第一个条目就是它。N.J.A.Sloane,Tableof50000digitsofelabeledfrom1to50000[基于下面的ICONProject链接]作者也是创建OEIS组织的N.J.ASloane。看来他是这个领域的大人物。抱歉,我不了解泰山。点击进入这个50000位的e的表格,标示为1到50000,页面效果很喜人。直接纯文本数据,左栏是小数位数,右栏是对应的值。届时,当获取到数据后,经过简单的处理就可以进行后续的工作。我希望这个证明题的答案在这50000个数字当中,不然范围又要扩大了。至此,e个无理数的小数位数据已经有了,可以进行下一步的工作了。第二步,如何判断一个数是素数?上小学的时候,数学老师教我们,素数的定义是指大于1的自然数,除了1和这个数本身,不能被其他自然数整除。那么自然而然,判断的方式就是判断2→n对于大于1的自然数n是否能整除n。如果发现一个数能整除n,那么n就不是质数,否则就是。此外,考虑到对称性,我们不必一直增加到n。比如2*3和3*2,6/2和6/3都判断6是合数,但是增加到2就够了,所以不用考虑3。Python代码如下:defisPrime(n:int)->bool:ifn<=1:returnFalsei=2#利用对称性。比如2*3=6,3*2=6whilei*i=5时,若n为素数,则n%6=1||n%6=5,即n必须出现在6x的两边(x≥1)。换句话说,任何素数都可以表示为6x±1,x∈N。证明:将6x附近的数表示为:......(6x-1),6x,6x+1,2(3x+1),3(2x+1),2(3x+2),6x+5,6(x+1)......不在6x两边的数是:2(3x+1),3(2x+1),2(3x+2),它们都不是素数,所以素数出现在6x的两边。用Python代码实现如下。时间复杂度和上一个差不多,但是对于我们的证明来说已经足够了。defisPrime(n:int)->bool:ifn<=1:returnFalseifn<=3:returnTrue#对于2(3x+1),3(2x+1),2(3x+2))ifn%2==0orn%3==0:returnFalse#对于素数相乘的情况i=5whilei*ibool:#素数定义版本:'''ifn<=1:returnFalsei=2#利用对称性。例如,2*3=6、3*2=6whilei*i