Re: [理工] 101清大/103交大離散質因數分解

看板Grad-ProbAsk作者a016258 (憨)時間8年前 (2017/03/30 10:38)推噓7(7推 0噓 13→)

留言20則, 5人參與討論串3/3 (看更多)

: : [ 101 清大資應 ] List the prime factors of 66043 : : [ 103 交大資訊 ] Find the prime factors of 820307 : : 恩.... : : 我看了這個題目然後再看了一下解答 : : 這種類型是不是就真的暴力下去一個一個找質因數阿... : : 可是答案質因數大的很誇張 : : 像是66043質因數分解出來是 211 x 313 : : 光是算到211應該是都要交卷了= = : : 還是說有甚麼快速的算法 : : 有大大知道這題的套路嗎? : 其實這題牽扯到數學系的數論部份了 : 在此小弟僅提供算法 : 如果想知道為什麼要這樣算…… : 麻煩自己估狗找數論質數部份XD : ㄧ、先隨便找ㄧ個平方數，愈接近題目給的愈好(這有點考驗數學的sense) : 二、找到第ㄧ個比題目給的數字大的數 : 三、減掉題目給的數字 : 四、剪完後的數字要是完全平方數(重點！！) : 五、找到後只要把你選的數字與減完的數字再開根號分別做相加跟相減就是答案了！ : http://i.imgur.com/DaxEqt7.jpg

: 這是ㄧ個非常神奇的地方，你減完跟加完的數字兩個數字都會是質數。 : 大概是這樣～手機排版請見諒 : 個人覺得會這個算法後雖然不難找但還是要花不少時間。但這種題目出的話分數都不會太 : 少…所以就評估自己當下狀況做選則吧xD 如果題目給的數字不是兩個大質數相乘的話這方法還可行嗎? ======================== 大概是國中的二年級講質因數的時候會有一個題目一個數 n , 如果無法被小於等於 sqrt(n) 的質數整除，則 n 為質數 <=> 如果 n 是合數，則可以找到一個質數小於等於 sqrt(n) ，且 n 被該質數整除 1. 256 < sqrt(66043) < 257 255 . 254 . 253 . 252 都不是質數 251 241 239 233 229 227 223 211... Zzzz 找到都天亮了 QQ 試試下一題 2. 905 < sqrt(820307) < 906 接著找比 906 小的質數 ...第一個質數為 887 可惜不是答案下一個為 883 bingo ! ( 交大數字雖大但好像比較有良心...) note: 計算過程中扣除容易判斷為合數需要確認是否為質數的有 901 899 897 893 891 889 把 29 23 19 17 13 11 7 拿下去除除看在計算是否為質數時會簡單一些不敢說一定比上一篇解法快僅供參考 Orz 有錯還請不吝指正。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.137.240 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1490841536.A.6C1.html

推

Re: [理工] 101清大/103交大 離散 質因數分解

Re: [理工] 101清大/103交大離散質因數分解