format_jam's pan

<< 宗教存在 与 个体行为 | 首 页 | 重游故地 >> 线性筛法求质数 - [ 算法+数据结构 ] 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