数字乘积

无心人

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

无心人

有点担心96#程序慢了 谁给优化下 因为程序在学校跑呢 所以在家就不想重写呢 想预先Cache幂 再进行乘积的提出 应该能提高很多很多 另外，似乎用10进制更好些 呵呵 ============================ 看目前的结果 在支持mathe的结论 似乎12阶以上数字的没有（包括非素数）

无心人

2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <gmp.h>
5. #include <math.h>
7. #define l2 1700
8. #define l3 1073
9. #define l7 605
11. mpz_t t3[l3 + 1], t7[l7 + 1], a, tn;
12. char out[1024];
13. unsigned int d[10][3];
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. }
33. int main(void)
34. {
35. unsigned int i, j, k;
36. int p = 0;
38. for (i = 0; i <= l3; i ++)
39. mpz_init(t3[i]);
41. for (i = 0; i <= l7; i ++)
42. mpz_init(t7[i]);
44. mpz_set_ui(t3[0], 1);
45. mpz_set_ui(t7[0], 1);
47. for (i = 1; i <= l3; i ++)
48. mpz_mul_ui(t3[i], t3[i - 1], 3);
50. for (i = 1; i <= l7; i ++)
51. mpz_mul_ui(t7[i], t7[i - 1], 7);
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);
75. for (i = 0; i <= l3; i ++)
76. mpz_clear(t3[i]);
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#是个很慢的程序 正在学校运行 怀疑明天到学校去的时候也完成不了

无心人

2. #include <stdio.h>
3. #include <stdlib.h>
4. #include <gmp.h>
5. #include <math.h>
7. #define l2 1700
8. #define l3 1073
9. #define l7 605
11. mpz_t a, b, tn;
12. char out[1024];
13. unsigned int d[10][3];
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. }
33. int main(void)
34. {
35. unsigned int i, j, k;
36. int p = 0;
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);
68. return 0;
69. }

复制代码

简化了下 不知道是否更好

gxqcn

1. #include <stdio.h>
3. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
4. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h" // 10进制系统
6. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
7. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
9. #define DIGIT_MAX 128
11. BOOL filter( const CHugeInt& hugeNum )
12. {
13. LPCTSTR p = (LPCTSTR)hugeNum;
14. BOOL b2 = FALSE;
16. do
17. {
18. if ( 0 == (((UINT32)*p) & 1) )
19. {
20. if ( '0' == *p )
21. {
22. return FALSE;
23. }
25. b2 = TRUE;
26. break;
27. }
28. else if ( '5' == *p )
29. {
30. break;
31. }
32. } while( NULL != *(++p) );
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. }
58. return TRUE;
59. }
61. int main(int argc, char* argv[])
62. {
63. UINT32 exp7, exp3, exp2, count = 0;
64. CHugeInt huge7, huge73, huge732;
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" );
74. system( "pause" );
75. return (-1);
76. }
78. HugeCalc::EnableTimer( TRUE );
79. HugeCalc::ResetTimer();
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. {
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. }
101. } while( ++exp2, ( huge732 *= 2 ).GetDigits() <= DIGIT_MAX );
103. } while( ++exp3, ( huge73 *= 3 ).GetDigits() <= DIGIT_MAX );
105. } while( ++exp7, ( huge7 *= 7 ).GetDigits() <= DIGIT_MAX );
107. printf( "\n****** %s ******\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
108. system( "pause" );
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 )
25. ****** 2.371397 s ******
26. 请按任意键继续. . .

复制代码

无心人

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