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

看板Grad-ProbAsk作者joy7658x348 (joy7658x348)時間7年前 (2017/03/29 17:31)推噓8(8推 0噓 3→)

留言11則, 9人參與討論串2/3 (看更多)

※ 引述《jerry900287 ()》之銘言： : 小弟在寫考古的時候 : 有兩題是這樣的 : [ 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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.170.65 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1490779866.A.AD0.html

→

joy7658x348

03/29 17:32, , 1^F

03/29 17:32, 1^F

推

shownlin

03/29 18:13, , 2^F

03/29 18:13, 2^F

→

joy7658x348

03/29 18:36, , 3^F

03/29 18:36, 3^F