想請問有關數學623質數的驗證問題----- @ bgdwze3的部落格

標題:

想請問有關數學623質數的驗證問題?????

發問:

欲判斷623是一個質數時~~最少要用2...3...5...等幾個質數除之才能確定?? 1.請問要用多少個質數??? 2.在623範圍內的質數~~光0~100就有25個質數了...為什麼可以確定說用幾個就可判別623是不是質數了??? 3.給我算法的公式~~ 4.拜託用比較容易懂的白話文~~講解一下他的公式算法 ps小弟資質較低~~需要白話註解~~小弟比較聽的懂!!!先謝謝了更新: 大大~~~可是答案最少要用2...3...5...等幾個質數除之才能確定?? 您還沒說阿???? 而且為什麼就用那幾個就能確定???多一個不行嗎??少一個不行嗎?? 更新 2: 你下面的補充解釋我懂了..1語點破...就是要用本身的數字開根號?? 可是....考場沒有計算機....請問623的根號要怎樣算出來是小於24.... 根號是代表....623的什麼數?? 更新 3: 哈哈哈~~~原來是平方.....可是根號還有很多種不是嗎??? 我前天還有一題開根號的...到現在還等沒高手要來解釋...有意願進來解釋看看嗎???http://tw.knowledge.yahoo.com/question/question?qid=1508012706037 您所教導的質數623我懂了.....假使質數888就慢慢用數值下去開平方...到最接近數之後...往回驗證她的質數有幾個...答案就出來了感謝您的回答喔~~~~~哈哈哈~~~我懂了

最佳解答:

欲判斷一個數 p 是否為質數，用小於等於 √p 的質數去除除看就可以知道了。 prove : 若一數 p 沒有辦法被小於等於 √p 的質數整除則 p 是質數 <=> 若 p 是合數，則 p 可以被小於等於√p 的質數整除 pf: 假設 p 是合數，則 p = ab . a . b 整除 a . b 或其中一個勢必小於等於 √p ( 若兩個都大於根號 p => a * b > √p * √p > p 矛盾 ) 所以可以被小於等於√p 的質數整除 ! # Ex . p= 221 . => √p 約等於 14.多所以從 13 開始測 221 = 13 * 17 所以他不是質數 -------------------------------------------- 由以上觀念 √623 約等於 24.... 所以檢查 23 . 19 . 17 . 13 . 11 . 7 . 5 . 3 . 2 發現 623 = 7 * 89 希望這樣說明你有懂囉。再給個例題 √713 約等於 26... 所以從比26小的質數開始檢查 23 ..... => 713 = 23 * 31 又網路上有不少人作了質數檢查器的東西搜尋一下有很多如果手邊有電腦的話可以考慮使用一下更快~~ 給個 http://www.life-tech.idv.tw/math/prime.htm 2008-01-27 21:40:38 補充：喔喔抱歉還沒回答到你的問題 √623 約等於 24.... 所以檢查 23 . 19 . 17 . 13 . 11 . 7 . 5 . 3 . 2 一共 9 個就可以了上面的證明不知道你有沒有看懂上面的證明再說一個數字 p 如果不能被小於等於根號 p 的質數整除的話他就是質數所以比根號623 小的質數一共 9 個 2008-01-27 21:41:55 補充：也就是比 23 大的質數都不用檢查了比小於等於 23的質數都要檢查有可能全部都不是有可能其中某一個是所以全部都要檢查~~ 希望這樣有回答到你的問題嚕~~ 2008-01-28 13:10:32 補充： ...你問根號是什麼... 這...XD 就是... 譬如說 25 是 5 的平方 => 則 √25 = 5 256 是 16 的平方 => √256 = 16 23的平方是 529 ， 24的平方是 576 ， 25的平方是 625 576 < 623 < 625 所以 √623 會比24大比25小所以從比 24...多小的質數開始檢查也就是 23 然後依序往下到 2...

其他解答: