难道是Bug？（我感觉很大程度上是）

gxqcn

小素数因子,郭肯定是有先筛除了,可能是筛的个数不同吧
qianyb 发表于 2010-7-26 07:36

这个观点是对的。

当前的做法是先排除1024以内的小素数因子，可能范围还不够。
如何选取范围，确实很纠结：太多了浪费，太少了筛选不足。
前者是针对小整数素性判定而言，后者则是针对超大整数而言。

看来，一个比较好的方案是：动态确定小素数因子排除范围，随被判定数的增大而增大（当然，得有个上封顶值）。

qianyb

我用hugeCalc测试了一下,用了1600秒找到,我也同时在做其它事情的

mathe

这个观点是对的。

当前的做法是先排除1024以内的小素数因子，可能范围还不够。
如何选取范围，确实很纠结：太多了浪费，太少了筛选不足。
前者是针对小整数素性判定而言，后者则是针对超大整数而言。

看 ...
gxqcn 发表于 2010-7-26 08:19

我说的筛法同排除小因子不同。
比如我们找NextPrime(x), 我觉得HugeCalc的做法可能是
for(x;!IsPrime(x);x++);
当然其中IsPrime(x)会先排除小因子，但是这样效率相对不高
如果我们该用筛法，可以先建立一个长度大概为N=k*log(x)的比特数组，用来表示
x,x+1,...,x+N-1
然后对于一定范围内的素数p采用筛法
也就是先计算x%p,然后找到最小的t使得p|x+t于是我们将x+t标为非素数，然后x+t+p,x+t+2p,...全部可以标为非素数，这样可以极大减少除法的数目。
当然，事先排除的小素数的数目也是有讲究的。
比如我们筛选了所有不超过P的素因子，我们可以估计余下的数大概在$N/{2ln(P)}$
如果还继续用下一个素数筛选，那么我们需要一次求模运算，N/P次比特数组访问，平均可以划去
$N/{2Pln(P)}$个合数。
如果假设计算一次求余的时钟在T1=100周期，一次比特访问T2=1个周期，而一次复杂的素数判定需要T3=10000个时钟周期.
那么应该在两种方法淘汰一个数的效率基本相等的时候我们应该切换到复杂的判定方法，也就是
${T1+T2*N/P}/{N/{2Pln(P)}}=T3$
对应到本题，也许应该可以筛选到数万（不过我这里采用的时钟周期估计不是很准，而且同x的具体值相关）

gxqcn

对于单个数的素性判定，先排除小因子；
而对于找相邻素数，我的算法基本与上述mathe描述的一致：
也是先建立了一个数组，采用筛法预先排除了一些，对于剩余的数无需再用小因子测定，直接调用复杂的素性判定。
只是当前“筛子”可能选得太小，效果不佳。

qianyb

HugeCalc查找大于$10^2000$的最小素数比查找小于$10^2000$的最大素数,两者的时间差太多了(1600秒:960秒),照理两者应该是差不多的

无心人

建议至少筛到2000内素数
此时，候选就会低于1/10了

无心人

筛法只能筛到某个小范围的素数为止
大了纯属浪费时间

282842712474

HugeCalc查找大于$10^2000$的最小素数比查找小于$10^2000$的最大素数,两者的时间差太多了(1600秒:960秒),照理两者应该是差不多的
qianyb 发表于 2010-7-26 12:33

我用HugeCalc查找大于$10^2000$的最小素数，609s，前300s还同时在浏览网页（IE7打开了7、8个标签），我的配置：
WinXP SP2


理论上应该很落后的配置了

silitex

算法真的是无止境啊！同时以崇高的敬意致敬楼主及所有楼上的人！你们的精神很让我佩服啊！

qianyb

18# 282842712474
那查找小于$10^2000$的最大素数用了多少时间?