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

[suhorng ( )]

你的寫法差不多呀=]]

(不過你修掉自己的推文……)

分享一下我的寫法XDDD

暴力檢查每個數是否是質數的話

p.s. 可以略的地方挺多的，例如一開始直接輸出 2, 然後 x 只跑奇數
     又如推廣的話可以直接略掉 2, 3 的倍數只檢查 6n+1, 6n-1 等
     在判斷質數的迴圈部份亦如是。

for (x=2; x<=1000; x++) {

     for (j=1; j*j <= x; j++);

     for (i=2; i<j; i++)
         if (x%i == 0) break;

     if (i >= j) printf("%d\n", x);

}

再來最常見的則是篩法 (略掉 2, 3 倍數後會比線性篩法略快)

bool not_prime[1001];

for (x=2; x<=1000; x++) {

     if (not_prime[x]) continue;

     printf("%d\n", x);

     for (i=x*x; i<=1000; i+=x)
         not_prime[i] = true;

}

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.137.68.118
推 bookticket:感謝分享~~~^^
→ VictorTom:小弟我就知道篩法一定會出現XD
→ suhorng:這還不是 6n+-1 ~"~ 不過差不多
→ tropical72:http://0rz.tw/i2IuV 參考一下.也歡迎指正
推 bookticket:也感謝樓上的分享~~^^
推 danielguo:篩法如果先建質數表的話會比較快~
推 tropical72:同意D大說法，但測試的話不是就該以沒建的情形測嗎？
→ danielguo:嗯, 我的話會先建到sqrt(n)的質數表 (跑一次也是),
→ danielguo:數字越大的話越有效果~ (n太小的話就沒用)
→ danielguo:變成跑兩次篩法, 先跑 sqrt(n) 再跑 n
推 tropical72:請教d大，那您第一次跑的 sqrt(n) 建表的方式
→ tropical72:是用經驗法則還是篩法？是用 6n+-1吧？
→ tropical72:不然感覺很像是在做篩法的 recursive..不知我有誤會嗎
推 danielguo:yeah, 可以說是recursive, 這樣最大的那次篩法會變快
→ danielguo:sqrt(n) 那次用什麼都可以 (數字少)
→ danielguo:啊, 篩法只有建質數表好用, 作判斷是不是質數不快
→ danielguo:hmm, 我剛試了一下, 好像篩法可能真的會比較慢 XDD
→ danielguo:啊, 剛改了個 bug, 現在篩法壓倒性的快了
推 tropical72:謝謝 D 大的指教 ^^
推 danielguo:不敢~ 我也是學了新用法