关于最大素数
来源：程序员人生 发布时间：2015-01-19 09:02:53 阅读次数：3063次
这些天很无聊的了解了1下几个数学题
由对王垠的40行代码引发，先是研究了尾递归，后又由于王垠的文章《谈P=NP？》了解了1下现今数学的7大困难，因而又去查其中1个庞加莱料想的事情（庞加莱料想已解决，后有丘成桐事件），另外哥德巴赫料想的相干事情（陈景润的1+2，非7大困难），最后又回到P/NP问题（7大困难之1），结果不谨慎又无聊的去查了1下最大素数问题，更无聊的是还随着去证明了1下。。。跟我的编程工作毫无关系嘛。。。我发现我的思惟也太散了。。。
关于最大素数问题
是不是有最大素数，下面是百度百科给出的证明进程：
不存在最大质数!
上小学的时候，我们就知道所有的自然数可以分为质数（素数）和合数两类，固然还特别规定了“1既不是质数，也不是合 数”。100之内的质数，从小到大顺次是：2、3、5、7、11、13、17、19、……、83、89、97。不用说了，你1定会背下来。那末质数的个数 是否是有限多的呢？
在解决这个问题之前，我们先来看看另外一个问题：怎样判断1个已知自然数是否是质数。比如，143是否是质数？
你1定会依照下面这个步骤去判断： 先用最小的质数2去除143，不能整除；再用3去试试，还是不行；再顺次用5、7试试，还是不行；11呢？行！143=11×13，所以143不是质数，而是合数。所以，判断1个数是否是质数，只需用比这个数小的所有质数，顺次去除它便可，如果都不能整除的话，这个数就1定是质数；相反，只要这个数能够被某1个质数整除，这个数就1定是合数。这类方法所根据的原理是：每个合数都可以表示成若干个质数的乘积。不用说，这叫做“分解质因数”，也是小学数学的知识。
我们先假定质数的个数是有限多的，那末必定存在1个“最大的质数”，设这个“最大的质数”为N。下面我们找出从1到N之间的所有质数，把它们连乘起来，就是：
2×3×5×7×11×13×……×N
把这个连乘积再加上1，得到1个相当大的数M：
M=2×3×5×7×11×13×……×N+1
那末这个M是质数还是合数呢？ 乍1想，不难判断，既然N是最大的质数，而且M>N，那末M就应当是合数。既然M是合数，就能够对M分解质因数。可是试1下就会发现，我们用从1到N之间的任何1个质数去除M，总是余1！这个现实，又表明M1定是质数。
这个自相矛盾的结果，不过说明： 最大的质数是不存在的！如果有1个足够大的质数N，1定可以像上面那样，找到1个比N更大的质数M。既然不存在最大的质数，就能够推知自然数中的质数应当有没有限多个。
可同时百度百科有人给出了另外一个反例：
M=2×3×5×7×11×13×……×N+1,用从1到N之间的任何1个质数去除M，总是余1！这个现实，又表明M1定是质数。此结论大错特错，例如，2×3×5×7×11×13+1=30031=59×509，30031是个合数。
看到这个反例，我开始怀疑以上证明的正确性，因而想了好久，终究想明白，该证明是正确的！
反例的毛病点在于他没有除比30031小的所有素数，仅除到13，而要证明1个素是不是素数必须要除比他小的所有素数均不能整除才可以证明该数是素数。
关于快速证明1个数是不是素数采取该数除以比他小的所有素数便可快速判断而无需除比他小的所有数，这个很好证明！每个合数必定可以表示成若干素数的乘积，1样很容易证明。这里不赘述。
我们之所以对以上证明进程存在质疑，主要来自于该证明的结论是N如果是最大素数，那末M还是素数。因而通过反例N=13，则M=30031，可30031是合数即M是合数，与上面的推论M是素数矛盾了！！这是怎样回事呢？是不是说明这个推论是毛病的呢？经过思考我们发现，证明中认定M是素数的条件是首先我们得认定N是最大的素数！！才推出M还是素数，然后自相矛盾，便可反证N不是最大素数。而反例中的条件条件即出错，N=13，明显13不是最大素数他就不可能成为N。
我们先不斟酌M和N谁比较大，按证明即先认定N为最大的素数，那末可推出M一定为素数这个结论。最后发现M>N，故N就不是最大素数。
然后再来看反例：”M=2×3×5×7×11×13×……×N+1,用从1到N之间的任何1个质数去除M，总是余1！这个现实，又表明M1定是质数。此结论大错特错，例如，2×3×5×7×11×13+1=30031=59×509，30031是个合数。“，其实M除以1到N总余1表示M1定是素数这个结论并没有错，由于这个结论的条件条件是N是我们假定的最大素数成立的条件，而不是指任意素数，作者混淆概念，如例子将13=N，推出出30031为M，而M不是素数所以颠覆结论，这条件条件就不正确了。
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
