估计下找到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. //////////////////////////////////////////////////////////////////////////
13. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
14. // Win32 Debug: Debug Multithreaded DLL
15. // Win32 Release: Multithreaded DLL
17. #include < iostream.h >
18. #include < fstream.h >
20. #include < HugeCalc.h > // 公共接口
21. #include < HugeInt.h > // 10进制系统
23. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
24. #pragma comment( lib, "HugeCalc.lib" )
26. int main(int argc, char* argv[])
27. {
28. cout << "Call " << HugeCalc::GetVer() << endl << endl;
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;
43. cout << "*** 搜索 10^r 后的四生素数 ***" << endl;
45. cout << "请输入 r = ";
46. cin >> r;
47. cout << endl;
49. cout << "请设定搜索组数：";
50. cin >> numb_max;
51. cout << endl;
53. if ( 0 == numb_max )
54. {
55. ++numb_max;
56. }
58. HugeCalc::EnableTimer();
59. HugeCalc::ResetTimer();
61. p.DecLShift( r );
62. p.NextPrime( p );
64. for ( ; ; )
65. {
66. p2.NextPrime( p );
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. }
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. }
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;
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. }
111. p.Swap( p8 );
112. }
113. }
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()){

复制代码

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