推 bookticket:也感謝樓上的分享~~^^ 09/14 23:11
推 danielguo:篩法如果先建質數表的話會比較快~ 09/14 23:34
推 tropical72:同意D大說法，但測試的話不是就該以沒建的情形測嗎？ 09/14 23:48
→ danielguo:嗯, 我的話會先建到sqrt(n)的質數表 (跑一次也是), 09/15 00:50
→ danielguo:數字越大的話越有效果~ (n太小的話就沒用) 09/15 00:50
→ danielguo:變成跑兩次篩法, 先跑 sqrt(n) 再跑 n 09/15 00:52
推 tropical72:請教d大，那您第一次跑的 sqrt(n) 建表的方式 09/15 01:56
→ tropical72:是用經驗法則還是篩法？是用 6n+-1吧？ 09/15 01:57
→ tropical72:不然感覺很像是在做篩法的 recursive..不知我有誤會嗎 09/15 01:57
推 danielguo:yeah, 可以說是recursive, 這樣最大的那次篩法會變快 09/15 03:09
→ danielguo:sqrt(n) 那次用什麼都可以 (數字少) 09/15 03:10
→ danielguo:啊, 篩法只有建質數表好用, 作判斷是不是質數不快 09/15 03:15
→ danielguo:hmm, 我剛試了一下, 好像篩法可能真的會比較慢 XDD 09/15 04:08
→ danielguo:啊, 剛改了個 bug, 現在篩法壓倒性的快了 09/15 04:34
推 tropical72:謝謝 D 大的指教 ^^ 09/15 04:37
推 danielguo:不敢~ 我也是學了新用法 09/15 04:51
噢 我還是不太懂就是了~"~
一個就是 http://0rz.tw/i2IuV 中的篩法用沒有避開偶數去跟有避開偶數的暴力法比較
如果篩法直接省略 2, 3 的倍數的話速度是很快的 篩到 10^7 在 0.2 秒內完成都沒問題
然後另外連結中的篩法是從 j = 2 而不是從 j = i*i 開始篩的，這樣速度差很多(默)
最不懂的是最後建質數表的地方Orz 如果使用篩法的話
建不建不都沒差了嗎 ? 反正也只要篩到 sqrt( n ) ，剩下的就是質數了呀
當然在某些題目適合建質數表，不過那是另一種狀況了吧 @____@a ?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.65.82
推 danielguo:可以試試看我上篇的寫法~ 用質數篩比避開 2, 3 篩還快 09/16 00:42
推 danielguo:hmm, 後來看其實質數分佈還蠻密的 09/16 06:54
→ danielguo:啊, 我搞錯 Sieve 的演算法了 09/16 08:18