Re: [語法] 尋找2~1000的質數 的語法討論

[bleed1979 (十三)]

※ 引述《suhorng ( )》之銘言：
: 標題: Re: [語法] 尋找2~1000的質數 的語法討論
: 時間: Tue Sep 15 19:15:28 2009
:
: 一個就是 http://0rz.tw/i2IuV 中的篩法用沒有避開偶數去跟有避開偶數的暴力法比較
:
: 如果篩法直接省略 2, 3 的倍數的話速度是很快的 篩到 10^7 在 0.2 秒內完成都沒問題
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 220.137.65.82
: 推 danielguo:可以試試看我上篇的寫法~ 用質數篩比避開 2, 3 篩還快    09/16 00:42

我把這兩個疑點寫成程式
篩6n+-1的方式和質數篩的方式

http://codepad.org/9CXqG2HO

n為2E8
篩完後輸出前1000個質數和最後一個質數

因為我沒有去Q質數篩的程式
所以不太敢說篩6n+-1一定比較快
只能說連結上的程式較快的是篩6n+-1
也許原作者可以試著在語法上改進質數篩的程式

兩個程式的基礎都在於6n+-1
問題在求質數與不求質數的這個動作


Bleed

--
World of bleed1979

http://bleed1979.myweb.hinet.net/


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.130.143.186
推 danielguo:喔喔~ 一邊篩一般用篩完得到的質數來篩
→ danielguo:嗯, 我的意思是不能單用 6n+-1 來篩
→ danielguo:你的 125 和 130 判斷了是不是質數, 所以兩者效果相近~
→ danielguo:邊篩邊用篩完的質數來篩看來是比較好的作法
→ danielguo:我搞錯 Sieve 的演算法了
→ bleed1979:其實因為對照你的寫法我沒有改變後篩的動作
→ bleed1979:for (k=i<<1,j=i*i;j<n;j+=k) 應該會再快一點點
→ suhorng:從 i*i 開始會快很多吧Orz
→ tropical72:很抱歉我寫了這篇錯誤的 blog 給各位參考
→ tropical72:在此例中我並沒有建立所謂的質數表是我的疏失
→ tropical72:同時也沒有把"線性篩法"的概念提到程式中