猜猜我的手机号码？

gxqcn

如果在已知：前三位为189，末两位为43，11个数字分别为：01123456789，且为两个素数之积，其中一素数为5位数。
则存在一些快速算法，比如说：

1、根据末两位为43，且为两素数之积，可先建立100内正奇数的乘法表，筛选出积末两位为43者的组合；

2、可先建立素数表，范围为：10000～1899999；

3、试算时，在确定一素数后，可以马上确定出另一素数的取值范围；

4、在计算出两素数乘积（需64位存储）后，可以马上减去18900000043，这样仅保留中间的6位数字，可以用DWORD类型数据存储；

5、在统计数字字符时，需要将数字转化为10进制字符，此处有些快速算法，可完全避免除法指令进行提速；或将012567六个数字全排列后排序，而后进行二分查找判定。

〇〇

31# gxqcn

请提供一个代码吧
我的代码已经用到了你的若干建议

gxqcn

具体代码我不想写了，结果应该在秒级内输出。

〇〇

具体代码我不想写了，结果应该在秒级内输出。
gxqcn 发表于 2009-8-25 13:04

我用30楼代码 if( temp>189e8 &&  temp<190e8 )还是9秒，不知道什么时候限制1出现2次
medie2005 的最大时间耗费是什么，int64的mod /运算？
你的建议中最大缩短时间是靠什么？

gxqcn

下面的代码，用了 STL，还调用了 HugeCalc 以快速生成素数表及统计耗时：

1. #include <iostream>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"    // 公共接口
   
6. 
   
7. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
   
8. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
   
9. 
   
10. 
    
11. int main(int argc, char* argv[])
    
12. {
    
13. //    printf("Hello World!\n");
    
14. 
    
15.     cout << "Call " << HugeCalc::GetVer() << endl << endl;
    
16. 
    
17.     // 初始化
    
18.     HugeCalc::EnableTimer( TRUE );
    
19.     HugeCalc::ResetTimer();
    
20. 
    
21.     UINT32 i, j;
    
22.     UINT32 u32Size = HugeCalc::GetPrimeCount( 10000, 1899999 );
    
23.     UINT32 * pPrimeBuffer = new UINT32[u32Size];
    
24.     HugeCalc::GetPrimeList( pPrimeBuffer, u32Size, 10000, 1899999 );
    
25. 
    
26.     UINT32 LUT[720], u32Dights[6] = { 0, 1, 2, 5, 6, 7 };
    
27.     UINT32 *p, *p1, *p2, *p_end;
    
28. 
    
29.     *( p = LUT ) = 1256743; /* 012567 43 */
    
30.     while( next_permutation( u32Dights, u32Dights+6 ))
    
31.     {
    
32.         for ( i=0, j=0; 6!=j; ++j )
    
33.         {
    
34.             i = i * 10 + u32Dights[j];
    
35.         }
    
36.         *(++p) = i * 100 + 43;
    
37.     }
    
38. 
    
39.     p1 = pPrimeBuffer;
    
40.     do
    
41.     {
    
42.         p2 = lower_bound( p1, pPrimeBuffer + u32Size, (UINT32)((UINT64)18901256743 / *p1 ));
    
43.         p_end = lower_bound( p2, pPrimeBuffer + u32Size, (UINT32)((UINT64)18976521043 / *p1 )+1 );
    
44. 
    
45.         do
    
46.         {
    
47.             i = (UINT32)( UInt32x32To64( *p1, *p2 ) - (UINT64)18900000000 );
    
48.             p = lower_bound( LUT, LUT+720, i );
    
49. 
    
50.             if ( LUT+720 != p && i == *p )
    
51.             {
    
52.                 cout << ((*p>=10000000)?"189":"1890") << *p << " = " << *p1 << " * " << *p2 << endl;
    
53.             }
    
54.         }while( p_end != ++p2 );
    
55. 
    
56.     } while( *(++p1) <= 99999 );
    
57. 
    
58.     delete []pPrimeBuffer;
    
59. 
    
60.     HugeCalc::EnableTimer( FALSE );
    
61. 
    
62.     cout << endl << "耗时为：" << HugeCalc::GetTimerStr( FT_DOT06SEC_s ) << endl;
    
63. 
    
64.     return 0;
    
65. }

复制代码

请将上述代码复制粘贴进 [..]\CopyrightByGuoXianqiang\HugeCalc\testDLL\src\ANSI_C++\ansi_c++.cpp，然后编译运行即可。

它运行速度非常快，结果如下：

1. Call HugeCalc V8.1.0.0 (Win32)
   
2. 
   
3. 18962715043 = 11173 * 1697191
   
4. 18960217543 = 13037 * 1454339
   
5. 18927156043 = 13187 * 1435289
   
6. 18952607143 = 13291 * 1425973
   
7. 18967512043 = 13799 * 1374557
   
8. 18926501743 = 13841 * 1367423
   
9. 18957201643 = 15077 * 1257359
   
10. 18962107543 = 16223 * 1168841
    
11. 18965210743 = 16631 * 1140353
    
12. 18950726143 = 17123 * 1106741
    
13. 18907561243 = 20357 * 928799
    
14. 18965710243 = 21023 * 902141
    
15. 18917062543 = 21817 * 867079
    
16. 18927615043 = 21893 * 864551
    
17. 18967102543 = 22247 * 852569
    
18. 18920516743 = 25183 * 751321
    
19. 18901652743 = 26501 * 713243
    
20. 18910725643 = 28657 * 659899
    
21. 18927610543 = 28807 * 657049
    
22. 18912076543 = 29269 * 646147
    
23. 18910765243 = 29569 * 639547
    
24. 18912576043 = 33773 * 559991
    
25. 18927160543 = 34351 * 550993
    
26. 18961270543 = 34367 * 551729
    
27. 18976105243 = 36527 * 519509
    
28. 18965172043 = 37309 * 508327
    
29. 18925160743 = 41981 * 450803
    
30. 18910625743 = 42131 * 448853
    
31. 18927016543 = 46171 * 409933
    
32. 18921567043 = 46867 * 403729
    
33. 18927561043 = 49463 * 382661
    
34. 18951207643 = 52201 * 363043
    
35. 18902756143 = 56893 * 332251
    
36. 18970162543 = 66509 * 285227
    
37. 18921675043 = 66571 * 284233
    
38. 18917065243 = 70957 * 266599
    
39. 18950126743 = 76603 * 247381
    
40. 18925671043 = 83101 * 227743
    
41. 18907652143 = 87049 * 217207
    
42. 18916705243 = 95891 * 197273
    
43. 18957062143 = 99023 * 191441
    
44. 
    
45. 耗时为：0.174513 s
    
46. Press any key to continue

复制代码

mathe

对于gxqcn的这个问题,总共才6!=720个候选数,我觉得直接因子分解它们可能会更加快

medie2005

分解用费马法即可.

mathe

其实这里试除也就可以了

mathe

用LiDIA写了个程序,不过发现速度不快6秒.这个应该是使用通用的因子分解算法的问题:

1. 
   
2. #include "LiDIA/bigint.h"
   
3. #include "LiDIA/rational_factorization.h"
   
4. #include <algorithm>
   
5. using namespace std;
   
6. using namespace LiDIA;
   
7. 
   
8. static int digitss[6]={0,1,2,5,6,7};
   
9. 
   
10. int main()
    
11. {
    
12.         int i,j;
    
13.         long long r;
    
14.         bigint v=1890;
    
15.         v*=10000000;
    
16.         do{
    
17.                 for(i=0,j=0;j!=6;j++){
    
18.                         i=i*10+digitss[j];
    
19.                 }
    
20.                 i=i*100+43;
    
21.                 bigint b=v+i;
    
22.                 rational_factorization fr(b);
    
23.                 fr.factor(3);
    
24.                 if(fr.no_of_comp()==2){
    
25.                         for(j=0;j<2;j++){
    
26.                                 if(fr.exponent(j)!=1)
    
27.                                         break;
    
28.                         }
    
29.                         if(j==2){
    
30.                                 bigint v1=fr.base(0);
    
31.                                 bigint v2=fr.base(1);
    
32.                                 if(v1>=10000&&v1<=10000000&&v2>=10000&&v2<=10000000){
    
33.                                         int u1,u2;
    
34.                                         v1.intify(u1);v2.intify(u2);
    
35.                                         printf("189%08d=%d*%d\n",i,u1,u2);
    
36.                                 }
    
37.                         }
    
38.                 }
    
39.         }while(next_permutation(digitss,digitss+6));
    
40. }
    

复制代码

不过结果有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

gxqcn

我的结果与 22# medie2005 的一致。
mathe 漏了一个限定条件：其中一个素因子为5位数。

虽然候选数不多，但试乘法比因子分解法效率高得多，所以我一开始就偏向于用试算法。