数字乘积

无心人

mathe能否分析下
2^p * 3^q * 7^r的数字里有5或者0的概率
如果可能，能否分析出什么p, q, r组合可以满足不是一步0

无心人

有点担心96#程序慢了

谁给优化下
因为程序在学校跑呢
所以在家就不想重写呢

想预先Cache幂
再进行乘积的提出

应该能提高很多很多
另外，似乎用10进制更好些
呵呵
============================
看目前的结果
在支持mathe的结论
似乎12阶以上数字的没有（包括非素数）

无心人

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <gmp.h>
   
5. #include <math.h>
   
6. 
   
7. #define l2 1700
   
8. #define l3 1073
   
9. #define l7 605
   
10. 
    
11. mpz_t t3[l3 + 1], t7[l7 + 1], a, tn;
    
12. char out[1024];
    
13. unsigned int d[10][3];
    
14. 
    
15. int filter(mpz_t tn)
    
16. {
    
17.   int e = 0, f = 0;
    
18.   char * c = out;
    
19.   mpz_get_str(out, 10, tn);
    
20. //  printf("%s\n", out);
    
21.   while (*c)
    
22.   {
    
23.     if (* c == '0')
    
24.       return 0;
    
25.     if (* c == '5') f = 1;
    
26.     if ((unsigned)(*c) % 2 == 0) e = 1;
    
27.     if ((f == 1) && (e == 1)) return 0;
    
28.     c ++;
    
29.   }
    
30.   return 1;  
    
31. }
    
32. 
    
33. int main(void)
    
34. {
    
35.   unsigned int i, j, k;
    
36.   int p = 0;
    
37. 
    
38.   for (i = 0; i <= l3; i ++)
    
39.     mpz_init(t3[i]);
    
40.   
    
41.   for (i = 0; i <= l7; i ++)
    
42.     mpz_init(t7[i]);
    
43. 
    
44.   mpz_set_ui(t3[0], 1);
    
45.   mpz_set_ui(t7[0], 1);
    
46. 
    
47.   for (i = 1; i <= l3; i ++)
    
48.     mpz_mul_ui(t3[i], t3[i - 1], 3);
    
49.   
    
50.   for (i = 1; i <= l7; i ++)
    
51.     mpz_mul_ui(t7[i], t7[i - 1], 7);
    
52. 
    
53.   mpz_init(tn);
    
54.   mpz_init(a);
    
55.   for (j = 0; j <= l3; j ++)
    
56.     for (k = 0; k <= l7; k ++)
    
57.     {
    
58.         mpz_mul(a, t3[j], t7[k]);
    
59.         for (i = 0; i <= l2; i ++)
    
60.           if (log10(2.0) * i + log10(3.0) * j + log10(7.0) * k <= 512.0)
    
61.           {
    
62.              mpz_mul_2exp(tn, a, i);
    
63.              if (filter(tn))
    
64.              {
    
65.                fprintf(stdout, "%u, %u, %u\n", i, j, k);
    
66.                fflush(stdout);
    
67.                p ++;
    
68.              }
    
69.           }
    
70.     }
    
71.   printf("Total: %u\n", p);
    
72.   mpz_clear(a);
    
73.   mpz_clear(tn);
    
74.   
    
75.   for (i = 0; i <= l3; i ++)
    
76.     mpz_clear(t3[i]);
    
77. 
    
78.   for (i = 0; i <= l7; i ++)  
    
79.     mpz_clear(t7[i]);
    
80.   return 0;
    
81. }
    

复制代码

也许这个程序速度快些

gxqcn

我可以写一个调用 HugeCalc 十进制内核的版本，但需要首先了解：

1、当前的算法或程序效率怎样？如果很快就可运行结束，就没有优化的必要了。

2、请大致讲解一些该段程序的目的，以及采用的算法原理，以便更好地优化。

无心人

就是测试n = 2^p * 3^q * 7^r
n 小于一个给定数字比如10^512
如果n的十进制表示中包含0或者同时有5和某个偶数则抛弃n
否则，输出p, q, r

无心人

102# 还可以再优化的

看512位内的结果情况
如果没有结果
也许优化了继续算到1000位

呵呵

无心人

候选者有上亿个呢
所以不可能很快就完成

96#是个很慢的程序
正在学校运行

怀疑明天到学校去的时候也完成不了

无心人

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <gmp.h>
   
5. #include <math.h>
   
6. 
   
7. #define l2 1700
   
8. #define l3 1073
   
9. #define l7 605
   
10. 
    
11. mpz_t a, b, tn;
    
12. char out[1024];
    
13. unsigned int d[10][3];
    
14. 
    
15. int filter(mpz_t tn)
    
16. {
    
17.   int e = 0, f = 0;
    
18.   char * c = out;
    
19.   mpz_get_str(out, 10, tn);
    
20. //  printf("%s\n", out);
    
21.   while (*c)
    
22.   {
    
23.     if (* c == '0')
    
24.       return 0;
    
25.     if (* c == '5') f = 1;
    
26.     if ((unsigned)(*c) % 2 == 0) e = 1;
    
27.     if ((f == 1) && (e == 1)) return 0;
    
28.     c ++;
    
29.   }
    
30.   return 1;  
    
31. }
    
32. 
    
33. int main(void)
    
34. {
    
35.   unsigned int i, j, k;
    
36.   int p = 0;
    
37. 
    
38.   mpz_init(tn);
    
39.   mpz_init(a);
    
40.   mpz_init(b);
    
41.   mpz_set_ui(a, 1);
    
42.   mpz_set_ui(b, 1);
    
43.   for (j = 0; j <= l3; j ++)
    
44.   {
    
45.     for (k = 0; k <= l7; k ++)
    
46.     {
    
47.         for (i = 0; i <= l2, log10(2.0) * i + log10(3.0) * j + log10(7.0) * k <= 512.0; i ++)
    
48.           {
    
49.              if (filter(tn))
    
50.              {
    
51.                fprintf(stdout, "%u, %u, %u\n", i, j, k);
    
52.                fflush(stdout);
    
53.                p ++;
    
54.              }
    
55.              mpz_mul_ui(tn, tn, 2);
    
56.           }
    
57.         mpz_mul_ui(b, b, 7);
    
58.         mpz_set(tn, b);
    
59.     }
    
60.     mpz_mul_ui(a, a, 3);
    
61.     mpz_set(b, a);
    
62.   }
    
63.   printf("Total: %u\n", p);
    
64.   mpz_clear(a);
    
65.   mpz_clear(b);
    
66.   mpz_clear(tn);
    
67.   
    
68.   return 0;
    
69. }
    

复制代码

简化了下
不知道是否更好

gxqcn

1. #include <stdio.h>
   
2. 
   
3. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"  // 公共接口
   
4. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"   // 10进制系统
   
5. 
   
6. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
   
7. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
   
8. 
   
9. #define DIGIT_MAX   128
   
10. 
    
11. BOOL filter( const CHugeInt& hugeNum )
    
12. {
    
13.     LPCTSTR p = (LPCTSTR)hugeNum;
    
14.     BOOL b2 = FALSE;
    
15. 
    
16.     do
    
17.     {
    
18.         if ( 0 == (((UINT32)*p) & 1) )
    
19.         {
    
20.             if ( '0' == *p )
    
21.             {
    
22.                 return FALSE;
    
23.             }
    
24. 
    
25.             b2 = TRUE;
    
26.             break;
    
27.         }
    
28.         else if ( '5' == *p )
    
29.         {
    
30.             break;
    
31.         }
    
32.     } while( NULL != *(++p) );
    
33. 
    
34.     if ( NULL != *p )
    
35.     {
    
36.         if ( b2 )
    
37.         {
    
38.             while ( NULL != *(++p) )
    
39.             {
    
40.                 if ( '0' == *p || '5' == *p )
    
41.                 {
    
42.                     return FALSE;
    
43.                 }
    
44.             }
    
45.         }
    
46.         else
    
47.         {
    
48.             while ( NULL != *(++p) )
    
49.             {
    
50.                 if ( 0 == (((UINT32)*p) & 1) )
    
51.                 {
    
52.                     return FALSE;
    
53.                 }
    
54.             }
    
55.         }
    
56.     }
    
57. 
    
58.     return TRUE;
    
59. }
    
60. 
    
61. int main(int argc, char* argv[])
    
62. {
    
63.     UINT32 exp7, exp3, exp2, count = 0;
    
64.     CHugeInt huge7, huge73, huge732;
    
65. 
    
66.     printf( "Call %s\n", HugeCalc::GetVer());
    
67.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
    
68.     {
    
69.         printf( "\n警告：您未通过 HugeCalc.dll 的许可认证！\n" \
    
70.                 "\n解决方案可选下列方案之一：" \
    
71.                 "\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
    
72.                 "\n    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。\n\n" );
    
73. 
    
74.         system( "pause" );
    
75.         return (-1);
    
76.     }
    
77. 
    
78.     HugeCalc::EnableTimer( TRUE );
    
79.     HugeCalc::ResetTimer();
    
80. 
    
81.     exp7 = 0;
    
82.     huge7 = 1;
    
83.     do
    
84.     {
    
85.         exp3 = 0;
    
86.         huge73 = huge7;
    
87.         do
    
88.         {
    
89.             exp2 = 0;
    
90.             huge732 = huge73;
    
91.             do
    
92.             {
    
93. 
    
94.                 if ( filter( huge732 ) )
    
95.                 {
    
96.                     fprintf(stdout, "%s  No.%u\texp( 2, 3, 7 ) = ( %u, %u, %u )\n",
    
97.                         HugeCalc::GetTimerStr( FT_HHMMSS_ms ), ++count, exp2, exp3, exp7 );
    
98.                     fflush(stdout);
    
99.                 }
    
100. 
     
101.             } while( ++exp2, ( huge732 *= 2 ).GetDigits() <= DIGIT_MAX );
     
102. 
     
103.         } while( ++exp3, ( huge73 *= 3 ).GetDigits() <= DIGIT_MAX );
     
104. 
     
105.     } while( ++exp7, ( huge7 *= 7 ).GetDigits() <= DIGIT_MAX );
     
106. 
     
107.     printf( "\n****** %s ******\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
     
108.     system( "pause" );
     
109. 
     
110.     return 0;
     
111. }

复制代码

上述代码经过了一些优化，效率非常高。
若将宏 DIGIT_MAX 定义成 128，则 2.371397 s 内就可得到全部 1105 组解：

1. . . .
   
2. 00:00:00.985  No.1084   exp( 2, 3, 7 ) = ( 7, 4, 20 )
   
3. 00:00:00.986  No.1085   exp( 2, 3, 7 ) = ( 43, 10, 20 )
   
4. 00:00:00.988  No.1086   exp( 2, 3, 7 ) = ( 51, 21, 20 )
   
5. 00:00:01.014  No.1087   exp( 2, 3, 7 ) = ( 5, 11, 21 )
   
6. 00:00:01.017  No.1088   exp( 2, 3, 7 ) = ( 16, 27, 21 )
   
7. 00:00:01.040  No.1089   exp( 2, 3, 7 ) = ( 12, 2, 22 )
   
8. 00:00:01.042  No.1090   exp( 2, 3, 7 ) = ( 36, 4, 22 )
   
9. 00:00:01.042  No.1091   exp( 2, 3, 7 ) = ( 20, 5, 22 )
   
10. 00:00:01.047  No.1092   exp( 2, 3, 7 ) = ( 9, 31, 22 )
    
11. 00:00:01.068  No.1093   exp( 2, 3, 7 ) = ( 15, 0, 23 )
    
12. 00:00:01.069  No.1094   exp( 2, 3, 7 ) = ( 4, 1, 23 )
    
13. 00:00:01.069  No.1095   exp( 2, 3, 7 ) = ( 5, 1, 23 )
    
14. 00:00:01.069  No.1096   exp( 2, 3, 7 ) = ( 8, 3, 23 )
    
15. 00:00:01.070  No.1097   exp( 2, 3, 7 ) = ( 7, 8, 23 )
    
16. 00:00:01.070  No.1098   exp( 2, 3, 7 ) = ( 21, 9, 23 )
    
17. 00:00:01.123  No.1099   exp( 2, 3, 7 ) = ( 5, 2, 25 )
    
18. 00:00:01.151  No.1100   exp( 2, 3, 7 ) = ( 5, 6, 26 )
    
19. 00:00:01.185  No.1101   exp( 2, 3, 7 ) = ( 1, 23, 27 )
    
20. 00:00:01.258  No.1102   exp( 2, 3, 7 ) = ( 26, 10, 30 )
    
21. 00:00:01.448  No.1103   exp( 2, 3, 7 ) = ( 19, 0, 38 )
    
22. 00:00:01.452  No.1104   exp( 2, 3, 7 ) = ( 4, 17, 38 )
    
23. 00:00:01.557  No.1105   exp( 2, 3, 7 ) = ( 14, 4, 43 )
    
24. 
    
25. ****** 2.371397 s ******
    
26. 请按任意键继续. . .

复制代码

无心人

确实很快

GMP的二进制内核的输出太慢了
导致过滤函数成为瓶颈