#22522: 為什麼可以用根號來解？
#22546: Re:為什麼可以用根號來解？
a121. 質數又來囉
| From: [218.35.40.37] |
發表日期
:
2020-09-14 01:47
小弟數學以及邏輯不大好
我知道跟號以後數字會變少，但是為什麼可以這樣操作呀？？？
還有要怎麼寫才會對？？？
求大神們解惑plz (一直卡在TLE QAQ)
這是判斷質數的方法，用一個 平方數 來說明看看，假設我今天要判斷 16 是不是 質數?
將他拿去對 2 , 3 , 4 , 5 , 6 , ... 一直到 16 的數作餘數判斷，最後得到了
16 = 1 x 16
2 x 8
4 x 4
你看，從 1 ~ 4 ，一直到 5 , 6 , 7 , 8 ...之後，如果有一個數 比如說是 8 能整除 16 ，那表示 一定還有一個整數 2 是能整除 16 的
從這觀點來判斷，假設今天判斷 17 是不是質數， 17 的開根號 等於 4.xxxx ，我們無條件進位到 5 給他
17 除 2 不整除，17 除 3 不整除，17 除 4 不整除，17 除 5 不整除，再往後作下去，妳根本找不到一個 大於 5 的數能整除 17 ，
然後 又有一個 小於 5 的數 相對應 來整除 17 ，所以基本上這個除法運算，作到 5 還沒有結果，就能直接判斷 17 是質數了。
以上，用這種方法來判斷質數，可以少掉不少步驟。
ZeroJudge Forum