作者suhorng ( )
看板C_and_CPP
標題Re: [語法] 尋找2~1000的質數 的語法討論
時間Mon Sep 14 21:31:20 2009
你的寫法差不多呀=]]
(不過你修掉自己的推文……)
分享一下我的寫法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
1F：推 bookticket:感謝分享~~~^^ 09/14 21:34
2F：→ VictorTom:小弟我就知道篩法一定會出現XD 09/14 21:35
3F：→ suhorng:這還不是 6n+-1 ~"~ 不過差不多 09/14 21:40
5F：推 bookticket:也感謝樓上的分享~~^^ 09/14 23:11
6F：推 danielguo:篩法如果先建質數表的話會比較快~ 09/14 23:34
7F：推 tropical72:同意D大說法，但測試的話不是就該以沒建的情形測嗎？ 09/14 23:48
8F：→ danielguo:嗯, 我的話會先建到sqrt(n)的質數表 (跑一次也是), 09/15 00:50
9F：→ danielguo:數字越大的話越有效果~ (n太小的話就沒用) 09/15 00:50
10F：→ danielguo:變成跑兩次篩法, 先跑 sqrt(n) 再跑 n 09/15 00:52
11F：推 tropical72:請教d大，那您第一次跑的 sqrt(n) 建表的方式 09/15 01:56
12F：→ tropical72:是用經驗法則還是篩法？是用 6n+-1吧？ 09/15 01:57
13F：→ tropical72:不然感覺很像是在做篩法的 recursive..不知我有誤會嗎 09/15 01:57
14F：推 danielguo:yeah, 可以說是recursive, 這樣最大的那次篩法會變快 09/15 03:09
15F：→ danielguo:sqrt(n) 那次用什麼都可以 (數字少) 09/15 03:10
16F：→ danielguo:啊, 篩法只有建質數表好用, 作判斷是不是質數不快 09/15 03:15
17F：→ danielguo:hmm, 我剛試了一下, 好像篩法可能真的會比較慢 XDD 09/15 04:08
18F：→ danielguo:啊, 剛改了個 bug, 現在篩法壓倒性的快了 09/15 04:34
19F：推 tropical72:謝謝 D 大的指教 ^^ 09/15 04:37
20F：推 danielguo:不敢~ 我也是學了新用法 09/15 04:51