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

[a016258 (憨)]

: : [ 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


有錯還請不吝指正。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.137.240
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1490841536.A.6C1.html
推 joy7658x348: 如果不是兩個質數相乘，那代表就是合數，合數就可以
13 不是兩個質數相乘 且 13並非合數

→ joy7658x348: 拆開來了，這樣答案應該會無限多種。這種題目應該都
→ joy7658x348: 只會問質數。例如１００可以拆成２*50 ，5*10等等，
→ joy7658x348: 這樣這種題目大家答案都不同，會造成批改困難。其實
List the prime factors ...

照題目意思 是把質因數列出來

所以 list the prime factors of 100 : 2 5



這種題目應該就是出兩個大質數相乘無誤


但我的疑問是 如果題目是出  23 * 79 * 293 =  532381

List the prime factors of 532381

你的方法無法找到答案 對嗎?


729 < sqrt(532381) < 730

看起來也沒法用開根號的方法了XD

但至少能找到答案(?)


→ joy7658x348: 只是在考驗大家計算小心程度而已吧…
→ joy7658x348: 10*10說錯……
※ 編輯: a016258 (140.114.137.240), 03/30/2017 12:18:32

剛想到 如果題目更沒良心的話

直接找一個大質數

問他的質因數 XDD
※ 編輯: a016258 (140.114.137.240), 03/30/2017 12:28:51
推 joy7658x348: 是的。這個算法只侷限在兩個質數相乘的時候。因為23*
→ joy7658x348: 79*293已經是三個質數相乘了，代表裡面任兩個數相乘
→ joy7658x348: 就不是質數了，就變成ㄧ個合數乘ㄧ個質數，所以這個
→ joy7658x348: 算法就不可行了～～謝謝提出問題點XD 但我覺得題目
→ joy7658x348: 考出來應該是有設計過的，不會殘忍到出三個質數相乘
→ joy7658x348: 的範例，如果真的有就送它吧哈哈！
推 joy7658x348: 第ㄧ句我所說的 不是兩個質數相乘就是合數 是指題目
→ joy7658x348: 給的數字，不是說直接給ㄧ個質數。造成誤會抱歉。
推 joy7658x348: 打的有點亂QQ 大家看看就好Orz 我只是講出我的想法(
→ joy7658x348: 汗)
推 jerry900287: 推!!! 有方法就是好方法 感恩
推 sarsman: 真的考出這種題目的話換角度想就是送分了，反正沒人會XD
現在你會了XD

你有兩個方法可以選

如果其他題完全沒什麼想法的話

這題又有個15.20分

留個半小時土法煉鋼一下吧~~

※ 編輯: a016258 (218.161.70.138), 03/30/2017 19:56:57
推 gaowei16: 這時後會超級心算多好
→ a016258: #1TtMbaGC (Math)