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

无心人

从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秒得到第一个结果

我计算的对么？

mathe

四生素数的定义：如果p,p+2,p+6,p+8都是素数，那么它们是四生素数。（通过google查到的）
计算没有什么错误，不过算法不是很好。
这个题目可以作为擂台赛。要求
对于一个输入的100位整数，要求在五分钟内用计算机找到不小于这个数的最小一组四生素数

无心人

你忒狠了啊

五分钟
可能么？

我计算过，以p1p2p3..pi*10*k + [1,3,7,9]的算法
只需要计算1/pi的数字
但是，差不容易计算

无心人

证明一个100位十进制的数字是素数，使用概率算法
时间绝对是大于1/2000秒的啊

就是说如果找到一个可能的结果，至少需1/500秒证明

无心人

上面是四生素数的分布估计

gxqcn

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: http://bbs.emath.ac.cn/
   
10. //
    
11. //////////////////////////////////////////////////////////////////////////
    
12. 
    
13. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
    
14. //      Win32 Debug:    Debug Multithreaded DLL
    
15. //      Win32 Release:  Multithreaded DLL
    
16. 
    
17. #include < iostream.h >
    
18. #include < fstream.h >
    
19. 
    
20. #include < HugeCalc.h > // 公共接口
    
21. #include < HugeInt.h >  // 10进制系统
    
22. 
    
23. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
    
24. #pragma comment( lib, "HugeCalc.lib" )
    
25. 
    
26. int main(int argc, char* argv[])
    
27. {
    
28.     cout << "Call " << HugeCalc::GetVer() << endl << endl;
    
29. 
    
30.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
    
31.     {
    
32.         cout << "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
    
33.             << "\r\n解决方案可选下列方案之一：" \
    
34.             << "\r\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
    
35.             << "\r\n    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" \
    
36.             << endl;
    
37.     }
    
38.     else
    
39.     {
    
40.         CHugeInt p( 1 ), p2, p6, p8, d;
    
41.         UINT32 r, numb = 0, numb_max, delta;
    
42. 
    
43.         cout << "*** 搜索 10^r 后的四生素数 ***"  << endl;
    
44. 
    
45.         cout << "请输入 r = ";
    
46.         cin >> r;
    
47.         cout << endl;
    
48. 
    
49.         cout << "请设定搜索组数：";
    
50.         cin >> numb_max;
    
51.         cout << endl;
    
52. 
    
53.         if ( 0 == numb_max )
    
54.         {
    
55.             ++numb_max;
    
56.         }
    
57. 
    
58.         HugeCalc::EnableTimer();
    
59.         HugeCalc::ResetTimer();
    
60. 
    
61.         p.DecLShift( r );
    
62.         p.NextPrime( p );
    
63. 
    
64.         for ( ; ; )
    
65.         {
    
66.             p2.NextPrime( p );
    
67. 
    
68.             delta = (UINT32)(( d = p2 ) -= p );
    
69.             if ( 2 == delta )
    
70.             {
    
71.                 p6.NextPrime( p2 );
    
72.             }
    
73.             else
    
74.             {
    
75.                 p.Swap( p2 );
    
76.                 continue;
    
77.             }
    
78. 
    
79.             delta = (UINT32)(( d = p6 ) -= p );
    
80.             if ( 6 == delta )
    
81.             {
    
82.                 p8.NextPrime( p6 );
    
83.             }
    
84.             else
    
85.             {
    
86.                 p.Swap(( 2 == delta ) ? p2 : p6 );
    
87.                 continue;
    
88.             }
    
89. 
    
90.             delta = (UINT32)(( d = p8 ) -= p );
    
91.             if ( 8 == delta )
    
92.             {
    
93.                 cout << "No." << ++numb << "\t" << HugeCalc::GetTimerStr() << endl;
    
94.                 cout << "  p = " << (LPCTSTR)p << endl;
    
95. 
    
96.                 if ( numb_max == numb )
    
97.                 {
    
98.                     cout << endl;
    
99.                     system( "pause" );
    
100.                     break;
     
101.                 }
     
102.                 else if ( 0 == ( numb & 15 ))
     
103.                 {
     
104.                     HugeCalc::EnableTimer( FALSE );
     
105.                     cout << endl;
     
106.                     system( "pause" );
     
107.                     HugeCalc::EnableTimer();
     
108.                 }
     
109.             }
     
110. 
     
111.             p.Swap( p8 );
     
112.         }
     
113.     }
     
114. 
     
115.     return 0;
     
116. }

复制代码

含源代码及编译好的程序压缩包： p4.zip (309.6 KB, 下载次数: 4)

2008-2-14 09:50 上传

点击文件名下载附件
四生素数快速搜索（含源代码）

mathe

呵呵，性能肯定不行

gxqcn

确实。
对于小点的 r，可以迅速得到解，权做一个数学小工具吧，方便对此有兴趣的朋友。

mathe

我给一个Reference Code，但是好像有点问题，不知道什么地方卡住了.
但是不知道为什么，我的机器上VC不能够调试程序，怎么设置都说没有调试信息
所以没办法找出原因，郭老大可以帮忙看一看:

游客，如果您要查看本帖隐藏内容请回复

gxqcn

问题出在“#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()){

复制代码

可以减少一些临时变量的构造与析构。