数学研发论坛

 找回密码
 欢迎注册
查看: 18587|回复: 69

[讨论] 估计下找到10^100以上的一个四生素数的工作量

[复制链接]
发表于 2008-2-13 17:21:12 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
从10^100开始
无限搜索下去
使用210k + [1, 10, 19] * 10 + [1, 3, 7, 9]形式
估计下,多长时间能搜索到一个四生素数

四生素数的分布概率有个公式,不记得在什么地方看到了
按照(1/100/ln10)^4算, 是1/28.11亿
搜索的速度是210/3 = 70

大概应该在1/28亿 * 70 = 1/4000万

计算一个100位数字是素数的时间是 < 1/200, 每组4个数字平均计算次数是< 1.5
则应该平均在4000万 * 1.5 / 200 = 6000 0000 / 200 = 3000000秒得到第一个结果

我计算的对么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-13 20:50:46 | 显示全部楼层
四生素数的定义:如果p,p+2,p+6,p+8都是素数,那么它们是四生素数。(通过google查到的)
计算没有什么错误,不过算法不是很好。
这个题目可以作为擂台赛。要求
对于一个输入的100位整数,要求在五分钟内用计算机找到不小于这个数的最小一组四生素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-14 08:00:50 | 显示全部楼层
你忒狠了啊

五分钟
可能么?

我计算过,以p1p2p3..pi*10*k + [1,3,7,9]的算法
只需要计算1/pi的数字
但是,差不容易计算
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-14 08:14:55 | 显示全部楼层
证明一个100位十进制的数字是素数,使用概率算法
时间绝对是大于1/2000秒的啊

就是说如果找到一个可能的结果,至少需1/500秒证明
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-14 08:39:02 | 显示全部楼层

上面是四生素数的分布估计
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 09:50:13 | 显示全部楼层

我写的程序

  1. //////////////////////////////////////////////////////////////////////////
  2. //
  3. // 目的:搜索 10^r 后的四生素数
  4. // 设计:郭先强 ( gxqcn@163.com; HugeCalc@Gmail.com )
  5. // 日期:2008-02-14
  6. // 备注:HugeCalc 暂未提供成片素数导出接口,否则会更快点:)
  7. //
  8. // Web: http://www.emath.ac.cn/
  9. // BBS: /
  10. //
  11. //////////////////////////////////////////////////////////////////////////

  12. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
  13. //      Win32 Debug:    Debug Multithreaded DLL
  14. //      Win32 Release:  Multithreaded DLL

  15. #include < iostream.h >
  16. #include < fstream.h >

  17. #include < HugeCalc.h > // 公共接口
  18. #include < HugeInt.h >  // 10进制系统

  19. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  20. #pragma comment( lib, "HugeCalc.lib" )

  21. int main(int argc, char* argv[])
  22. {
  23.     cout << "Call " << HugeCalc::GetVer() << endl << endl;

  24.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
  25.     {
  26.         cout << "\r\n警告:您未通过 HugeCalc.dll 的许可认证!\r\n" \
  27.             << "\r\n解决方案可选下列方案之一:" \
  28.             << "\r\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行;" \
  29.             << "\r\n    二、或请在 HugeCalc.chm 中进行注册(一劳永逸)。" \
  30.             << endl;
  31.     }
  32.     else
  33.     {
  34.         CHugeInt p( 1 ), p2, p6, p8, d;
  35.         UINT32 r, numb = 0, numb_max, delta;

  36.         cout << "*** 搜索 10^r 后的四生素数 ***"  << endl;

  37.         cout << "请输入 r = ";
  38.         cin >> r;
  39.         cout << endl;

  40.         cout << "请设定搜索组数:";
  41.         cin >> numb_max;
  42.         cout << endl;

  43.         if ( 0 == numb_max )
  44.         {
  45.             ++numb_max;
  46.         }

  47.         HugeCalc::EnableTimer();
  48.         HugeCalc::ResetTimer();

  49.         p.DecLShift( r );
  50.         p.NextPrime( p );

  51.         for ( ; ; )
  52.         {
  53.             p2.NextPrime( p );

  54.             delta = (UINT32)(( d = p2 ) -= p );
  55.             if ( 2 == delta )
  56.             {
  57.                 p6.NextPrime( p2 );
  58.             }
  59.             else
  60.             {
  61.                 p.Swap( p2 );
  62.                 continue;
  63.             }

  64.             delta = (UINT32)(( d = p6 ) -= p );
  65.             if ( 6 == delta )
  66.             {
  67.                 p8.NextPrime( p6 );
  68.             }
  69.             else
  70.             {
  71.                 p.Swap(( 2 == delta ) ? p2 : p6 );
  72.                 continue;
  73.             }

  74.             delta = (UINT32)(( d = p8 ) -= p );
  75.             if ( 8 == delta )
  76.             {
  77.                 cout << "No." << ++numb << "\t" << HugeCalc::GetTimerStr() << endl;
  78.                 cout << "  p = " << (LPCTSTR)p << endl;

  79.                 if ( numb_max == numb )
  80.                 {
  81.                     cout << endl;
  82.                     system( "pause" );
  83.                     break;
  84.                 }
  85.                 else if ( 0 == ( numb & 15 ))
  86.                 {
  87.                     HugeCalc::EnableTimer( FALSE );
  88.                     cout << endl;
  89.                     system( "pause" );
  90.                     HugeCalc::EnableTimer();
  91.                 }
  92.             }

  93.             p.Swap( p8 );
  94.         }
  95.     }

  96.     return 0;
  97. }
复制代码
含源代码及编译好的程序压缩包: p4.zip (309.6 KB, 下载次数: 4)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 09:54:27 | 显示全部楼层
呵呵,性能肯定不行
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 10:13:04 | 显示全部楼层
确实。
对于小点的 r,可以迅速得到解,权做一个数学小工具吧,方便对此有兴趣的朋友。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 11:03:32 | 显示全部楼层
我给一个Reference Code,但是好像有点问题,不知道什么地方卡住了.
但是不知道为什么,我的机器上VC不能够调试程序,怎么设置都说没有调试信息
所以没办法找出原因,郭老大可以帮忙看一看:
游客,如果您要查看本帖隐藏内容请回复
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-14 11:34:00 | 显示全部楼层
问题出在“#define SET_MASK(x)  (mask[(x)>>5]|=1<<((x)&31))”宏定义上,其中的 x 并未被修改,
致使如下代码(也许是这里的问题)进入死循环:
  1.             int h;
  2.             for(h=s;h<RANGE;s+=p){
  3.                 SET_MASK(h);///Filter hugeStart+h*30
  4.             }
复制代码
非常佩服你将 HugeCalc 运用得如此熟练。

一点建议:
  1.            if((hugeStart-4).IsPrime()&&
  2.                 (hugeStart-2).IsPrime()&&
  3.                 (hugeStart+2).IsPrime()&&
  4.                 (hugeStart+4).IsPrime()){
复制代码
修改成:
  1.             integer hugeTmp( hugeStart );
  2.             if((hugeTmp-=4).IsPrime()&&
  3.                 (hugeTmp+=2).IsPrime()&&
  4.                 (hugeTmp+=4).IsPrime()&&
  5.                 (hugeTmp+=2).IsPrime()){
复制代码
可以减少一些临时变量的构造与析构。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-12-9 23:20 , Processed in 0.068841 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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