作者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