關于最大素數
來源：程序員人生 發布時間：2015-01-19 09:02:53 閱讀次數：3232次
這些天很無聊的了解了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不是素數所以顛覆結論，這條件條件就不正確了。
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
