找回密码
 欢迎注册
楼主: mathe

[擂台] 连续自然数构成的素数

[复制链接]
 楼主| 发表于 2008-4-23 13:44:33 | 显示全部楼层
那36583你的机器运行了多长时间?不过感觉我用的这台台式机性能还没有我的笔记本好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-23 14:15:33 | 显示全部楼层

回复 5# 的帖子

你就直接说是3的倍数更好理解,看了半天才明白555。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-23 16:57:05 | 显示全部楼层

对 6 楼代码的一点小改进

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;

  7.             if ( !buff[j] )
  8.             {
  9.                 x.DecLShift( tail.GetDigits() );
  10.                 x += tail;
  11.                 tail = 0;

  12.                 if ( x.IsPrime())
  13.                 {
  14.                     printf("Found: %s\n",x.GetStr());
  15.                     count++;
  16.                 }
  17.             }
复制代码
改进后仅在需要时才移位追加新的数字,减少大整数的移位次数,
之前则用一个长度较小的 tail 处理(它的移位代价要小得多)。

在我的机器上,前端的 filter 需要很长很长时间才能准备完成。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-23 17:28:30 | 显示全部楼层


是否做过小因子分解

每个数字是否存在有规律的小因子

那样能排除一大批数字
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-23 17:30:57 | 显示全部楼层


我猜测在10^8以内存在一个素数
对应数字应该大于10^100000000

所以该问题应该提交到大型机
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-23 17:37:02 | 显示全部楼层
原帖由 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小时
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-23 17:38:35 | 显示全部楼层


5个小时算少的
我运行GIMPS一个多月才能判定一个梅森数呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-23 17:40:41 | 显示全部楼层
要不然你运行一下看看,假设我上面估计估计不错,也就是两个月左右可以穷举到100000,有11%可能性能够找到一个素数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-23 17:42:20 | 显示全部楼层


你加上定时存盘和冗余纠错
我给你挂服务器上三个月
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-23 17:42:49 | 显示全部楼层
原帖由 gogdizzy 于 2008-4-23 14:15 发表
你就直接说是3的倍数更好理解,看了半天才明白555。

呵呵,你可以将它当成一种练习
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 13:22 , Processed in 0.047002 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表