估计下找到10^100以上的一个四生素数的工作量
一个比较好的论坛话题从10^100开始无限搜索下去
使用210k + * 10 + 形式
估计下，多长时间能搜索到一个四生素数
四生素数的分布概率有个公式，不记得在什么地方看到了
按照(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秒得到第一个结果
我计算的对么？ 四生素数的定义：如果p,p+2,p+6,p+8都是素数，那么它们是四生素数。（通过google查到的）
计算没有什么错误，不过算法不是很好。
这个题目可以作为擂台赛。要求
对于一个输入的100位整数，要求在五分钟内用计算机找到不小于这个数的最小一组四生素数 你忒狠了啊
五分钟
可能么？
我计算过，以p1p2p3..pi*10*k + 的算法
只需要计算1/pi的数字
但是，差不容易计算 证明一个100位十进制的数字是素数，使用概率算法
时间绝对是大于1/2000秒的啊
就是说如果找到一个可能的结果，至少需1/500秒证明 http://primes.utm.edu/gifs/HardyLittlewood4.gif
上面是四生素数的分布估计
我写的程序
////////////////////////////////////////////////////////////////////////////
// 目的：搜索 10^r 后的四生素数
// 设计：郭先强 ( gxqcn@163.com; HugeCalc@Gmail.com )
// 日期：2008-02-14
// 备注：HugeCalc 暂未提供成片素数导出接口，否则会更快点:)
//
// Web: http://www.emath.ac.cn/
// BBS: http://bbs.emath.ac.cn/
//
//////////////////////////////////////////////////////////////////////////
// Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
// Win32 Debug: Debug Multithreaded DLL
// Win32 Release:Multithreaded DLL
#include < iostream.h >
#include < fstream.h >
#include < HugeCalc.h > // 公共接口
#include < HugeInt.h >// 10进制系统
#pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "HugeCalc.lib" )
int main(int argc, char* argv[])
{
cout << "Call " << HugeCalc::GetVer() << endl << endl;
if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
{
cout << "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
<< "\r\n解决方案可选下列方案之一：" \
<< "\r\n 一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
<< "\r\n 二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" \
<< endl;
}
else
{
CHugeInt p( 1 ), p2, p6, p8, d;
UINT32 r, numb = 0, numb_max, delta;
cout << "*** 搜索 10^r 后的四生素数 ***"<< endl;
cout << "请输入 r = ";
cin >> r;
cout << endl;
cout << "请设定搜索组数：";
cin >> numb_max;
cout << endl;
if ( 0 == numb_max )
{
++numb_max;
}
HugeCalc::EnableTimer();
HugeCalc::ResetTimer();
p.DecLShift( r );
p.NextPrime( p );
for ( ; ; )
{
p2.NextPrime( p );
delta = (UINT32)(( d = p2 ) -= p );
if ( 2 == delta )
{
p6.NextPrime( p2 );
}
else
{
p.Swap( p2 );
continue;
}
delta = (UINT32)(( d = p6 ) -= p );
if ( 6 == delta )
{
p8.NextPrime( p6 );
}
else
{
p.Swap(( 2 == delta ) ? p2 : p6 );
continue;
}
delta = (UINT32)(( d = p8 ) -= p );
if ( 8 == delta )
{
cout << "No." << ++numb << "\t" << HugeCalc::GetTimerStr() << endl;
cout << "p = " << (LPCTSTR)p << endl;
if ( numb_max == numb )
{
cout << endl;
system( "pause" );
break;
}
else if ( 0 == ( numb & 15 ))
{
HugeCalc::EnableTimer( FALSE );
cout << endl;
system( "pause" );
HugeCalc::EnableTimer();
}
}
p.Swap( p8 );
}
}
return 0;
}含源代码及编译好的程序压缩包： 呵呵，性能肯定不行:) 确实。
对于小点的 r，可以迅速得到解，权做一个数学小工具吧，方便对此有兴趣的朋友。:) 我给一个Reference Code，但是好像有点问题，不知道什么地方卡住了.
但是不知道为什么，我的机器上VC不能够调试程序，怎么设置都说没有调试信息:L
所以没办法找出原因，郭老大可以帮忙看一看:
**** Hidden Message ***** 问题出在“#define SET_MASK(x)(mask[(x)>>5]|=1<<((x)&31))”宏定义上，其中的 x 并未被修改，
致使如下代码（也许是这里的问题）进入死循环： int h;
for(h=s;h<RANGE;s+=p){
SET_MASK(h);///Filter hugeStart+h*30
}非常佩服你将 HugeCalc 运用得如此熟练。
一点建议： if((hugeStart-4).IsPrime()&&
(hugeStart-2).IsPrime()&&
(hugeStart+2).IsPrime()&&
(hugeStart+4).IsPrime()){修改成： integer hugeTmp( hugeStart );
if((hugeTmp-=4).IsPrime()&&
(hugeTmp+=2).IsPrime()&&
(hugeTmp+=4).IsPrime()&&
(hugeTmp+=2).IsPrime()){可以减少一些临时变量的构造与析构。