如果在已知：前三位为189，末两位为43，11个数字分别为：01123456789，且为两个素数之积，其中一素数为5位数。
则存在一些快速算法，比如说：
1、根据末两位为43，且为两素数之积，可先建立100内正奇数的乘法表，筛选出积末两位为43者的组合；
2、可先建立素数表，范围为：10000～1899999；
3、试算时，在确定一素数后，可以马上确定出另一素数的取值范围；
4、在计算出两素数乘积（需64位存储）后，可以马上减去18900000043，这样仅保留中间的6位数字，可以用DWORD类型数据存储；
5、在统计数字字符时，需要将数字转化为10进制字符，此处有些快速算法，可完全避免除法指令进行提速；或将012567六个数字全排列后排序，而后进行二分查找判定。
31# gxqcn
请提供一个代码吧
我的代码已经用到了你的若干建议
具体代码我不想写了，结果应该在秒级内输出。
具体代码我不想写了，结果应该在秒级内输出。
gxqcn 发表于 2009-8-25 13:04 http://bbs.emath.ac.cn/images/common/back.gif
我用30楼代码 if( temp>189e8 &&temp<190e8 )还是9秒，不知道什么时候限制1出现2次
medie2005 的最大时间耗费是什么，int64的mod /运算？
你的建议中最大缩短时间是靠什么？
下面的代码，用了 STL，还调用了 HugeCalc 以快速生成素数表及统计耗时：#include <iostream>
#include <algorithm>
using namespace std;
#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
#pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
int main(int argc, char* argv[])
{
// printf("Hello World!\n");
cout << "Call " << HugeCalc::GetVer() << endl << endl;
// 初始化
HugeCalc::EnableTimer( TRUE );
HugeCalc::ResetTimer();
UINT32 i, j;
UINT32 u32Size = HugeCalc::GetPrimeCount( 10000, 1899999 );
UINT32 * pPrimeBuffer = new UINT32;
HugeCalc::GetPrimeList( pPrimeBuffer, u32Size, 10000, 1899999 );
UINT32 LUT, u32Dights = { 0, 1, 2, 5, 6, 7 };
UINT32 *p, *p1, *p2, *p_end;
*( p = LUT ) = 1256743; /* 012567 43 */
while( next_permutation( u32Dights, u32Dights+6 ))
{
for ( i=0, j=0; 6!=j; ++j )
{
i = i * 10 + u32Dights;
}
*(++p) = i * 100 + 43;
}
p1 = pPrimeBuffer;
do
{
p2 = lower_bound( p1, pPrimeBuffer + u32Size, (UINT32)((UINT64)18901256743 / *p1 ));
p_end = lower_bound( p2, pPrimeBuffer + u32Size, (UINT32)((UINT64)18976521043 / *p1 )+1 );
do
{
i = (UINT32)( UInt32x32To64( *p1, *p2 ) - (UINT64)18900000000 );
p = lower_bound( LUT, LUT+720, i );
if ( LUT+720 != p && i == *p )
{
cout << ((*p>=10000000)?"189":"1890") << *p << " = " << *p1 << " * " << *p2 << endl;
}
}while( p_end != ++p2 );
} while( *(++p1) <= 99999 );
delete []pPrimeBuffer;
HugeCalc::EnableTimer( FALSE );
cout << endl << "耗时为：" << HugeCalc::GetTimerStr( FT_DOT06SEC_s ) << endl;
return 0;
}请将上述代码复制粘贴进 [..]\CopyrightByGuoXianqiang\HugeCalc\testDLL\src\ANSI_C++\ansi_c++.cpp，然后编译运行即可。
它运行速度非常快，结果如下：Call HugeCalc V8.1.0.0 (Win32)
18962715043 = 11173 * 1697191
18960217543 = 13037 * 1454339
18927156043 = 13187 * 1435289
18952607143 = 13291 * 1425973
18967512043 = 13799 * 1374557
18926501743 = 13841 * 1367423
18957201643 = 15077 * 1257359
18962107543 = 16223 * 1168841
18965210743 = 16631 * 1140353
18950726143 = 17123 * 1106741
18907561243 = 20357 * 928799
18965710243 = 21023 * 902141
18917062543 = 21817 * 867079
18927615043 = 21893 * 864551
18967102543 = 22247 * 852569
18920516743 = 25183 * 751321
18901652743 = 26501 * 713243
18910725643 = 28657 * 659899
18927610543 = 28807 * 657049
18912076543 = 29269 * 646147
18910765243 = 29569 * 639547
18912576043 = 33773 * 559991
18927160543 = 34351 * 550993
18961270543 = 34367 * 551729
18976105243 = 36527 * 519509
18965172043 = 37309 * 508327
18925160743 = 41981 * 450803
18910625743 = 42131 * 448853
18927016543 = 46171 * 409933
18921567043 = 46867 * 403729
18927561043 = 49463 * 382661
18951207643 = 52201 * 363043
18902756143 = 56893 * 332251
18970162543 = 66509 * 285227
18921675043 = 66571 * 284233
18917065243 = 70957 * 266599
18950126743 = 76603 * 247381
18925671043 = 83101 * 227743
18907652143 = 87049 * 217207
18916705243 = 95891 * 197273
18957062143 = 99023 * 191441
耗时为：0.174513 s
Press any key to continue
对于gxqcn的这个问题,总共才6!=720个候选数,我觉得直接因子分解它们可能会更加快
分解用费马法即可.
其实这里试除也就可以了
用LiDIA写了个程序,不过发现速度不快6秒.这个应该是使用通用的因子分解算法的问题:
#include "LiDIA/bigint.h"
#include "LiDIA/rational_factorization.h"
#include <algorithm>
using namespace std;
using namespace LiDIA;
static int digitss={0,1,2,5,6,7};
int main()
{
int i,j;
long long r;
bigint v=1890;
v*=10000000;
do{
for(i=0,j=0;j!=6;j++){
i=i*10+digitss;
}
i=i*100+43;
bigint b=v+i;
rational_factorization fr(b);
fr.factor(3);
if(fr.no_of_comp()==2){
for(j=0;j<2;j++){
if(fr.exponent(j)!=1)
break;
}
if(j==2){
bigint v1=fr.base(0);
bigint v2=fr.base(1);
if(v1>=10000&&v1<=10000000&&v2>=10000&&v2<=10000000){
int u1,u2;
v1.intify(u1);v2.intify(u2);
printf("189%08d=%d*%d\n",i,u1,u2);
}
}
}
}while(next_permutation(digitss,digitss+6));
}
不过结果有46个,同gxqcn不完全相同
18901652743=26501*713243
18902756143=56893*332251
18907561243=20357*928799
18907652143=87049*217207
18910625743=42131*448853
18910725643=28657*659899
18910765243=29569*639547
18912065743=111521*169583
18912076543=29269*646147
18912576043=33773*559991
18916705243=95891*197273
18917062543=21817*867079
18917065243=70957*266599
18920516743=25183*751321
18920716543=108947*173669
18921567043=46867*403729
18921675043=66571*284233
18925160743=41981*450803
18925671043=83101*227743
18926501743=13841*1367423
18927016543=46171*409933
18927156043=13187*1435289
18927160543=34351*550993
18927561043=49463*382661
18927610543=28807*657049
18927615043=21893*864551
18950126743=76603*247381
18950621743=121139*156437
18950726143=17123*1106741
18951207643=52201*363043
18952607143=13291*1425973
18957062143=99023*191441
18957201643=15077*1257359
18960217543=13037*1454339
18961027543=109507*173149
18961270543=34367*551729
18962107543=16223*1168841
18962715043=11173*1697191
18965172043=37309*508327
18965210743=16631*1140353
18965710243=21023*902141
18967102543=22247*852569
18967512043=13799*1374557
18970162543=66509*285227
18972506143=112501*168643
18976105243=36527*519509
我的结果与 22# medie2005 的一致。
mathe 漏了一个限定条件：其中一个素因子为5位数。
虽然候选数不多，但试乘法比因子分解法效率高得多，所以我一开始就偏向于用试算法。