论坛 › 算法交流 › 连续逆素数

无心人 发表于 2008-6-17 14:20:05

你这个是什么算法得到的？

mathe 发表于 2008-6-17 14:21:38

原帖由 无心人 于 2008-6-17 14:19 发表 http://bbs.emath.ac.cn/images/common/back.gif
因为，大数的逆序基本上都分散的很开
假设无关联

则连续10个过100素数的概率是1/ln(1000)^10 = 4.4E-9
你要计算的是至少一个过100素数的概率，还是挺大的。不过作为一种筛选的手段，应该还是可以使用的

无心人 发表于 2008-6-17 14:27:09

我觉得超过32bit的用强行筛选的方法应该不会慢

无心人 发表于 2008-6-17 14:28:53

假设有一个区间
首先筛得到素数

然后对素数求逆序，筛100内素数
如果过，则标1，否则标0

连续有10个以上1的，进行中间数字的测试
然后再测试其他的

mathe 发表于 2008-6-17 14:29:09

是的，应该还行。
不知道medie2005是不是就是采用分段筛法做的？

无心人 发表于 2008-6-17 14:33:10

你作下试试

不会用到大数算法的
很简单的

大不了最后过下米勒－罗宾测试

medie2005 发表于 2008-6-17 14:38:19

对10^9内的长度为10的连续素数集，mathe前面给的结果好像漏了一组：
{924408493,924408497,924408517,924408521,924408559,924408587,924408601,924408607,
924408613,924408619}

medie2005 发表于 2008-6-17 14:40:05

我的算法还是分段筛。

无心人 发表于 2008-6-17 15:06:59

看来简单的还是最好的

mathe 发表于 2008-6-17 17:07:52

原帖由 medie2005 于 2008-6-17 14:38 发表 http://bbs.emath.ac.cn/images/common/back.gif
对10^9内的长度为10的连续素数集，mathe前面给的结果好像漏了一组：
{924408493,924408497,924408517,924408521,924408559,924408587,924408601,924408607,
924408613,924408619}
程序长度颠倒代码有个bug,数据第五位是0的时候有错,需要修改一下

查看完整版本: 连续逆素数