孤城 10 發表於 February 4, 2007 檢舉 Share 發表於 February 4, 2007 平時我們要證明一個數是質數，我們可以從2.3.5.7....等一一檢驗例如103不是2.3.5.7的倍數，則為一質數不過我想問的是，萬一此數很大呢？例如614889782588491411總不可能從2.3.5.7...一一去驗證吧，那樣太花時間了是否有什麼方法可以在短時間內證明此數為一質數？ 鏈接文章 分享到其他網站
代名詞 10 發表於 February 4, 2007 檢舉 Share 發表於 February 4, 2007 我記得有個方法...就是找他平方根最近的數字的因數一一找尋例如231 離他最近的平方數是225 從1~15的質數一一下去找...我不知道我講的是不會完全正確= = 有點忘記的話 請見諒 鏈接文章 分享到其他網站
孤城 10 發表於 February 4, 2007 作者 檢舉 Share 發表於 February 4, 2007 我記得有個方法...就是找他平方根最近的數字的因數一一找尋例如231 離他最近的平方數是225 從1~15的質數一一下去找...我不知道我講的是不會完全正確= = 有點忘記的話 請見諒我前面舉的103的例子就是你說的那個方法不過當數字很大的時候，用這個方法會花很多時間吧@@所以我想問的是是否有其他更快的方法能檢定很大的數字是否為質數 鏈接文章 分享到其他網站
清風明月 10 發表於 February 4, 2007 檢舉 Share 發表於 February 4, 2007 那個叫做"篩法"是一般中學生常用的工具至於有沒有"較快"的算法讓電腦去跑好了XD如果方法很快卻難懂的話那我就不知道有什麼其他數論的東西了 鏈接文章 分享到其他網站
tw00088437 10 發表於 February 5, 2007 檢舉 Share 發表於 February 5, 2007 (以後也不一定會有)要電腦把兩個100位的質數乘起來,不到1秒鐘的事但是要把這個乘積給電腦質因數分解,電腦所做的事跟我們做的是一樣的----從2開始的質數一個一個檢驗,所以乘法公式和因式分解這兩個互逆的操作電腦花的時間可是大不相同!要把一個200位的數分成兩個100位的質數乘積超級電腦也要費上好幾(十?)年工夫的.不然以現在一些質數檢驗網站為例,你打的數字越大,就可明顯感受到操作時間變長.你打個幾百億的數字近去包准他當機給你看.如果同學們能找出更好的方法保證是數學界最偉大的成就之一 ^^||| 鏈接文章 分享到其他網站
tw00088437 10 發表於 February 5, 2007 檢舉 Share 發表於 February 5, 2007 也因此目前找出一個最大的質數才會是個需要公諸世人的大事呀...^^ 鏈接文章 分享到其他網站
殘風~缺月~半日 10 發表於 February 6, 2007 檢舉 Share 發表於 February 6, 2007 目前來說這種事情是還沒有更新的方法出現最最最快的方法就是一個一個代就對啦 鏈接文章 分享到其他網站
訪客 發表於 February 7, 2007 檢舉 Share 發表於 February 7, 2007 質數可以拿來作機密用途就是這樣因為兩個很大的質數一乘起來就分不開了聽說在有些國家很大的質數是機密...... 鏈接文章 分享到其他網站
jacafe 10 發表於 February 9, 2007 檢舉 Share 發表於 February 9, 2007 不知道能不能用"歸謬法"來證它是否為質數(因為現在也只有學到"篩法"和"歸謬法"兩種而已) 鏈接文章 分享到其他網站
孤城 10 發表於 February 11, 2007 作者 檢舉 Share 發表於 February 11, 2007 sor我把例子的數字改一下= =a其實我舉的例子是要舉質數(雖然我不曉得現在改的這個是不是質數)我想了一個質數輾轉檢驗法，不過只是構想，實際上我不曉得是否所有的數皆能成立我先列出100以前的質數2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97然後按順序相乘2x3=62x3x5=302x3x5x7=2102x3x5x7x11=23102x3x5x7x11x13x17=39270....2x3x5x7x11x13x17x19x23x29x31x37x41x43x47=614889782588491410先以2311為例子如果我們要檢驗2311是否為質數則用上表找出最接近且小於2311的數來跟2311作輾轉相除法得結果其最大公因數為1，則可知2311無法被2,3,5,7,11整除由此類推我舉的例子614889782588491411跟614889782588491410作輾轉相除不過這和篩法似乎有矛盾，因為篩法是要以比其數平方根小的整數一一檢定而2311只檢定到了2,3,5,7,11若嚴謹一點則應該用2x3x5x7x11x13x17x19x23=223092870來做輾轉相除才對而且用這方法要查表我想這方法的出發點是用手算，完全沒考慮到計算機xd第一次打到一半不小心把網頁關了T^T，這次打的可能看起來會比較簡略 鏈接文章 分享到其他網站
夢境的行旅 10 發表於 February 13, 2007 檢舉 Share 發表於 February 13, 2007 注意!!!!!!這個「篩法」只是看起來合理而已，但完全不是這麼一回事。注意到了嗎？最接近的那一項根本不代表表內質數連乘積和他有相同的質因數啊。例如說2*3*5*7*11*13=30030 現在找一個數 3^6*41=29889 那個41根本是前面沒出現過的高斯(或是歐拉，反正兩者都是心算超強的怪才)，空閒時間的娛樂是找出所有「千數」(例如13000～14000)當中的所有質數，他的方法當然不是一個一個的篩，而是利用自己導出的，數論中的強大公式(對我們門外漢來講是天書的，例如費馬小定理)，一次把範圍縮小到－－我也不知道－－幾十個數吧。但是我想，他的方法八成失傳了，因為對天才數學家他們來說這些只不過是雕蟲小技......讀了關於數論的科普書之後的心得 鏈接文章 分享到其他網站
Arcson 10 發表於 February 13, 2007 檢舉 Share 發表於 February 13, 2007 sor我把例子的數字改一下= =a其實我舉的例子是要舉質數(雖然我不曉得現在改的這個是不是質數)我想了一個質數輾轉檢驗法，不過只是構想，實際上我不曉得是否所有的數皆能成立我先列出100以前的質數2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97然後按順序相乘2x3=62x3x5=302x3x5x7=2102x3x5x7x11=23102x3x5x7x11x13x17=39270....2x3x5x7x11x13x17x19x23x29x31x37x41x43x47=614889782588491410先以2311為例子如果我們要檢驗2311是否為質數則用上表找出最接近且小於2311的數來跟2311作輾轉相除法得結果其最大公因數為1，則可知2311無法被2,3,5,7,11整除由此類推我舉的例子614889782588491411跟614889782588491410作輾轉相除不過這和篩法似乎有矛盾，因為篩法是要以比其數平方根小的整數一一檢定而2311只檢定到了2,3,5,7,11若嚴謹一點則應該用2x3x5x7x11x13x17x19x23=223092870來做輾轉相除才對而且用這方法要查表我想這方法的出發點是用手算，完全沒考慮到計算機xd第一次打到一半不小心把網頁關了T^T，這次打的可能看起來會比較簡略我覺得這樣能證明的也只是614889782588491411跟614889782588491410互質吧並沒有證明614889782588491411是個質數 鏈接文章 分享到其他網站
rm2slg 10 發表於 February 15, 2007 檢舉 Share 發表於 February 15, 2007 以下假設加減乘除運算極快：設待測數為p利用Wilson定理，將(p-1)!對p取餘數，若餘數為-1，則此數為質數 鏈接文章 分享到其他網站
孤城 10 發表於 February 17, 2007 作者 檢舉 Share 發表於 February 17, 2007 我覺得這樣能證明的也只是614889782588491411跟614889782588491410互質吧並沒有證明614889782588491411是個質數我是想說2x3x5x7x11x13x17x19x23x29x31x37x41x43x47=614889782588491410那麼和他互質的數必不為2,3,5,7,11,13,17,19,23,29,31,37,41,43,47的倍數若有一數的平方根之最接近的比他小之數為47例如2301(純舉例，非質數)，本來用篩法的話是要從2,3,5,......,43,47一一檢定但若直接和614889782588491410作輾轉相除便可以一次做完篩法 鏈接文章 分享到其他網站
demipenguin 10 發表於 February 28, 2007 檢舉 Share 發表於 February 28, 2007 想法本身是沒有錯的但是這樣子電腦運算會有限制以篩法來說，最高位數就是要檢驗的質數但是你的做法是一大串數相乘以我所知最大的質數2^32582657-1來說它有9808358位小於他的全部質數相乘根據質數定理小於n的質數個數p(n)在n很大時0.92129(n / ln n)< p(n) <1.10555(n / ln n)n=e^22584576代入(約等於2^32582657-1)p(n)大約10^8炸掉了 鏈接文章 分享到其他網站
cyp 10 發表於 March 2, 2007 檢舉 Share 發表於 March 2, 2007 以下假設加減乘除運算極快：設待測數為p利用Wilson定理，將(p-1)!對p取餘數，若餘數為-1，則此數為質數如果運算極快，可能用篩法還要更快些！:s 鏈接文章 分享到其他網站
cyp 10 發表於 March 2, 2007 檢舉 Share 發表於 March 2, 2007 平時我們要證明一個數是質數，我們可以從2.3.5.7....等一一檢驗例如103不是2.3.5.7的倍數，則為一質數不過我想問的是，萬一此數很大呢？例如614889782588491411總不可能從2.3.5.7...一一去驗證吧，那樣太花時間了是否有什麼方法可以在短時間內證明此數為一質數？如果你找到了什麼很快的方法，就算沒有得fields medal，大概也離數學大師不遠了！:) 鏈接文章 分享到其他網站
Recommended Posts
請登入後來留意見
在登入之後,您才能留意見
立即登入