: : [ 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
有错还请不吝指正。