: : [ 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
有錯還請不吝指正。