format_jam's pan
jambo · 2007-11-12
<< 宗教存在 与 个体行为
|
首 页
|
重游故地 >>
线性筛法求质数
- [
算法+数据结构
]
2007-10-26
没有看错,你绝对没有看错。xre
borner把筛法改进为线性了!!!
今天论坛转载了这个贴http://bbs.sysu.edu.cn/bbstcon?board=ACMICPC&file=M.1193279150.A
这个算法的改进针对筛法里面的重大缺陷的:对同一个合数往往重复标记多次!(改进为1次)而且实现还非常简单,强烈推荐!!!
关键代码:
for (i=2;i<=n;i++)
{
if (a[i]==0)
{
num++;p[num]=i;
}
for (j=1;((j<=num) && (i*p[j]<=n)); j++)
{
a[i*p[j]] = 1 ;
if (i%p[j] == 0) break;
}
}
回忆:
开始我们逐个除,然后梁老教我们除到N^(1/2) ,后来是筛法,现在是线性!
真的是无极限啊!!!
随机文章:
USU Open Personal Contest 2008
2008-03-02
查找序列中 元素之和最大的连续子序列 的一次扫描法 &&左右扫描思想
2007-11-16
Summary: 遗传算法(GA) 粒子群优化(PSO)
2007-10-06
Thinking out of the box 线性排序算法的启示
2007-08-15
c++字符串宝典
2007-06-17
收藏到:
Del.icio.us
Tag:
算法
筛法
求质数
引用地址:
发表于
00:27:59
|
编辑
|
继续话题
|
转发
|
推荐
评论
其实
我感觉我以前一直都是这么做的
还是觉得 艺术 里面那个概率判断比较牛b
回复
xt3000
说:
这跟我们以前用的筛法是不同的,你看看那个实现就知道了。。。真的是每个数只赋值一次。难道说你以前一直知道有这么好的方法不告诉我。。。
概率判断?我去看看
2007-11-12 20:38:45
xt3000
|
[
回复
]
看不懂。。~
對了~煎包~生日快樂ar~.*
回复
Bu
说:
嘻嘻~同樣祝BOA生日快樂ar~.*
2007-11-05 23:28:56
Bu |
[
回复
]
发表评论
原始快照:web.archive.org