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

[joy7658x348 (joy7658x348)]

※ 引述《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: *擇
推 shownlin: 推，超詳細
→ joy7658x348: 大家可以用交大那題練習看看，不懂歡迎站內
推 yupog2003: 學習了，原來還是有個較為通用的方法
推 sarsman: 推!!原來還有這招
推 jerry900287: 有神快拜阿XD
推 darren0831: 推XDDD 好險今年沒考不然我會算到死
推 gaowei16: 已學到，謝謝分享
→ gaowei16: 平方差的應用
推 fancycab: 這解法太神了....跪一波感謝
推 Aa841018: 這個太厲害了！
推 try66889: 推推超神><