连续自然数构成的素数

mathe

那36583你的机器运行了多长时间？不过感觉我用的这台台式机性能还没有我的笔记本好

gogdizzy

你就直接说是3的倍数更好理解，看了半天才明白555。

gxqcn

将 6# 如下代码：

1. integer x("123456789");
2. for(i=2;i<=6;i++){
3. for(j=k;j<10*k;j++){
4. x*=k*10;
5. x+=j;
6. if((!buff[j])&&x.IsPrime()){
7. printf("Found: %s\n",x.GetStr());
8. count++;
9. }

复制代码

改成：

1. integer x("123456789");
2. integer tail;
3. for(i=2;i<=6;i++){
4. for(j=k;j<10*k;j++){
5. tail.DecLShift( i );
6. tail += j;
8. if ( !buff[j] )
9. {
10. x.DecLShift( tail.GetDigits() );
11. x += tail;
12. tail = 0;
14. if ( x.IsPrime())
15. {
16. printf("Found: %s\n",x.GetStr());
17. count++;
18. }
19. }

复制代码

改进后仅在需要时才移位追加新的数字，减少大整数的移位次数， 之前则用一个长度较小的 tail 处理（它的移位代价要小得多）。 在我的机器上，前端的 filter 需要很长很长时间才能准备完成。。。

无心人

是否做过小因子分解 每个数字是否存在有规律的小因子 那样能排除一大批数字

无心人

我猜测在10^8以内存在一个素数 对应数字应该大于10^100000000 所以该问题应该提交到大型机

mathe

原帖由 mathe 于 2008-4-23 12:18 发表 这三个数有什么特殊的？好像都挺慢 8053素性判断需要8.1分钟,10279需要16.3分钟,36583还没有运行出来，到出来再看吧

晕36583运行了5小时差4分钟出来了。

原帖由 无心人 于 2008-4-23 17:30 发表 我猜测在10^8以内存在一个素数 对应数字应该大于10^100000000 所以该问题应该提交到大型机

上面的程序中已经将所有包含小于100000因子的数事先筛选了，（而且我试验过事先筛选1000000以内的因子，区别不大）。而现在主要问题在于对于这些超大数据，素性判断太慢了，比如上面的36583要运行5小时

无心人

5个小时算少的 我运行GIMPS一个多月才能判定一个梅森数呢

mathe

要不然你运行一下看看，假设我上面估计估计不错，也就是两个月左右可以穷举到100000,有11%可能性能够找到一个素数。

无心人

你加上定时存盘和冗余纠错 我给你挂服务器上三个月

mathe

原帖由 gogdizzy 于 2008-4-23 14:15 发表 你就直接说是3的倍数更好理解，看了半天才明白555。

呵呵，你可以将它当成一种练习