作者joy7658x348 (joy7658x348)
看板Grad-ProbAsk
标题Re: [理工] 101清大/103交大 离散 质因数分解
时间Wed Mar 29 17:31:03 2017
※ 引述《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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1490779866.A.AD0.html
1F：→ joy7658x348: *择 03/29 17:32
2F：推 shownlin: 推，超详细 03/29 18:13
3F：→ joy7658x348: 大家可以用交大那题练习看看，不懂欢迎站内 03/29 18:36
4F：推 yupog2003: 学习了，原来还是有个较为通用的方法 03/29 18:52
5F：推 sarsman: 推!!原来还有这招 03/29 22:32
6F：推 jerry900287: 有神快拜阿XD 03/30 00:27
7F：推 darren0831: 推XDDD 好险今年没考不然我会算到死 03/30 00:44
8F：推 gaowei16: 已学到，谢谢分享 04/01 12:51
9F：→ gaowei16: 平方差的应用 04/01 14:27
10F：推 fancycab: 这解法太神了....跪一波感谢 12/13 21:21
11F：推 Aa841018: 这个太厉害了！ 12/26 08:58
12F：推 try66889: 推推超神>< 12/19 13:45