2^p * 3^q * 7^r的数字里有5或者0的概率
如果可能，能否分析出什么p, q, r组合可以满足不是一步0 有点担心96#程序慢了
谁给优化下
因为程序在学校跑呢
所以在家就不想重写呢
想预先Cache幂
再进行乘积的提出
应该能提高很多很多
另外，似乎用10进制更好些
呵呵
============================
看目前的结果
在支持mathe的结论
似乎12阶以上数字的没有（包括非素数）
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <math.h>
#define l2 1700
#define l3 1073
#define l7 605
mpz_t t3, t7, a, tn;
char out;
unsigned int d;
int filter(mpz_t tn)
{
int e = 0, f = 0;
char * c = out;
mpz_get_str(out, 10, tn);
//printf("%s\n", out);
while (*c)
{
if (* c == '0')
return 0;
if (* c == '5') f = 1;
if ((unsigned)(*c) % 2 == 0) e = 1;
if ((f == 1) && (e == 1)) return 0;
c ++;
}
return 1;
}
int main(void)
{
unsigned int i, j, k;
int p = 0;
for (i = 0; i <= l3; i ++)
mpz_init(t3);
for (i = 0; i <= l7; i ++)
mpz_init(t7);
mpz_set_ui(t3, 1);
mpz_set_ui(t7, 1);
for (i = 1; i <= l3; i ++)
mpz_mul_ui(t3, t3, 3);
for (i = 1; i <= l7; i ++)
mpz_mul_ui(t7, t7, 7);
mpz_init(tn);
mpz_init(a);
for (j = 0; j <= l3; j ++)
for (k = 0; k <= l7; k ++)
{
mpz_mul(a, t3, t7);
for (i = 0; i <= l2; i ++)
if (log10(2.0) * i + log10(3.0) * j + log10(7.0) * k <= 512.0)
{
mpz_mul_2exp(tn, a, i);
if (filter(tn))
{
fprintf(stdout, "%u, %u, %u\n", i, j, k);
fflush(stdout);
p ++;
}
}
}
printf("Total: %u\n", p);
mpz_clear(a);
mpz_clear(tn);
for (i = 0; i <= l3; i ++)
mpz_clear(t3);
for (i = 0; i <= l7; i ++)
mpz_clear(t7);
return 0;
}
也许这个程序速度快些 我可以写一个调用 HugeCalc 十进制内核的版本，但需要首先了解：
1、当前的算法或程序效率怎样？如果很快就可运行结束，就没有优化的必要了。
2、请大致讲解一些该段程序的目的，以及采用的算法原理，以便更好地优化。 就是测试n = 2^p * 3^q * 7^r
n 小于一个给定数字比如10^512
如果n的十进制表示中包含0或者同时有5和某个偶数则抛弃n
否则，输出p, q, r 102# 还可以再优化的
看512位内的结果情况
如果没有结果
也许优化了继续算到1000位
呵呵 候选者有上亿个呢
所以不可能很快就完成
96#是个很慢的程序
正在学校运行
怀疑明天到学校去的时候也完成不了
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
#include <math.h>
#define l2 1700
#define l3 1073
#define l7 605
mpz_t a, b, tn;
char out;
unsigned int d;
int filter(mpz_t tn)
{
int e = 0, f = 0;
char * c = out;
mpz_get_str(out, 10, tn);
//printf("%s\n", out);
while (*c)
{
if (* c == '0')
return 0;
if (* c == '5') f = 1;
if ((unsigned)(*c) % 2 == 0) e = 1;
if ((f == 1) && (e == 1)) return 0;
c ++;
}
return 1;
}
int main(void)
{
unsigned int i, j, k;
int p = 0;
mpz_init(tn);
mpz_init(a);
mpz_init(b);
mpz_set_ui(a, 1);
mpz_set_ui(b, 1);
for (j = 0; j <= l3; j ++)
{
for (k = 0; k <= l7; k ++)
{
for (i = 0; i <= l2, log10(2.0) * i + log10(3.0) * j + log10(7.0) * k <= 512.0; i ++)
{
if (filter(tn))
{
fprintf(stdout, "%u, %u, %u\n", i, j, k);
fflush(stdout);
p ++;
}
mpz_mul_ui(tn, tn, 2);
}
mpz_mul_ui(b, b, 7);
mpz_set(tn, b);
}
mpz_mul_ui(a, a, 3);
mpz_set(b, a);
}
printf("Total: %u\n", p);
mpz_clear(a);
mpz_clear(b);
mpz_clear(tn);
return 0;
}
简化了下
不知道是否更好
优化 102# 无心人 的程序
#include <stdio.h>#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"// 公共接口
#include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h" // 10进制系统
#pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#define DIGIT_MAX 128
BOOL filter( const CHugeInt& hugeNum )
{
LPCTSTR p = (LPCTSTR)hugeNum;
BOOL b2 = FALSE;
do
{
if ( 0 == (((UINT32)*p) & 1) )
{
if ( '0' == *p )
{
return FALSE;
}
b2 = TRUE;
break;
}
else if ( '5' == *p )
{
break;
}
} while( NULL != *(++p) );
if ( NULL != *p )
{
if ( b2 )
{
while ( NULL != *(++p) )
{
if ( '0' == *p || '5' == *p )
{
return FALSE;
}
}
}
else
{
while ( NULL != *(++p) )
{
if ( 0 == (((UINT32)*p) & 1) )
{
return FALSE;
}
}
}
}
return TRUE;
}
int main(int argc, char* argv[])
{
UINT32 exp7, exp3, exp2, count = 0;
CHugeInt huge7, huge73, huge732;
printf( "Call %s\n", HugeCalc::GetVer());
if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
{
printf( "\n警告：您未通过 HugeCalc.dll 的许可认证！\n" \
"\n解决方案可选下列方案之一：" \
"\n 一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
"\n 二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。\n\n" );
system( "pause" );
return (-1);
}
HugeCalc::EnableTimer( TRUE );
HugeCalc::ResetTimer();
exp7 = 0;
huge7 = 1;
do
{
exp3 = 0;
huge73 = huge7;
do
{
exp2 = 0;
huge732 = huge73;
do
{
if ( filter( huge732 ) )
{
fprintf(stdout, "%sNo.%u\texp( 2, 3, 7 ) = ( %u, %u, %u )\n",
HugeCalc::GetTimerStr( FT_HHMMSS_ms ), ++count, exp2, exp3, exp7 );
fflush(stdout);
}
} while( ++exp2, ( huge732 *= 2 ).GetDigits() <= DIGIT_MAX );
} while( ++exp3, ( huge73 *= 3 ).GetDigits() <= DIGIT_MAX );
} while( ++exp7, ( huge7 *= 7 ).GetDigits() <= DIGIT_MAX );
printf( "\n****** %s ******\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
system( "pause" );
return 0;
}上述代码经过了一些优化，效率非常高。
若将宏 DIGIT_MAX 定义成 128，则 2.371397 s 内就可得到全部 1105 组解：. . .
00:00:00.985No.1084 exp( 2, 3, 7 ) = ( 7, 4, 20 )
00:00:00.986No.1085 exp( 2, 3, 7 ) = ( 43, 10, 20 )
00:00:00.988No.1086 exp( 2, 3, 7 ) = ( 51, 21, 20 )
00:00:01.014No.1087 exp( 2, 3, 7 ) = ( 5, 11, 21 )
00:00:01.017No.1088 exp( 2, 3, 7 ) = ( 16, 27, 21 )
00:00:01.040No.1089 exp( 2, 3, 7 ) = ( 12, 2, 22 )
00:00:01.042No.1090 exp( 2, 3, 7 ) = ( 36, 4, 22 )
00:00:01.042No.1091 exp( 2, 3, 7 ) = ( 20, 5, 22 )
00:00:01.047No.1092 exp( 2, 3, 7 ) = ( 9, 31, 22 )
00:00:01.068No.1093 exp( 2, 3, 7 ) = ( 15, 0, 23 )
00:00:01.069No.1094 exp( 2, 3, 7 ) = ( 4, 1, 23 )
00:00:01.069No.1095 exp( 2, 3, 7 ) = ( 5, 1, 23 )
00:00:01.069No.1096 exp( 2, 3, 7 ) = ( 8, 3, 23 )
00:00:01.070No.1097 exp( 2, 3, 7 ) = ( 7, 8, 23 )
00:00:01.070No.1098 exp( 2, 3, 7 ) = ( 21, 9, 23 )
00:00:01.123No.1099 exp( 2, 3, 7 ) = ( 5, 2, 25 )
00:00:01.151No.1100 exp( 2, 3, 7 ) = ( 5, 6, 26 )
00:00:01.185No.1101 exp( 2, 3, 7 ) = ( 1, 23, 27 )
00:00:01.258No.1102 exp( 2, 3, 7 ) = ( 26, 10, 30 )
00:00:01.448No.1103 exp( 2, 3, 7 ) = ( 19, 0, 38 )
00:00:01.452No.1104 exp( 2, 3, 7 ) = ( 4, 17, 38 )
00:00:01.557No.1105 exp( 2, 3, 7 ) = ( 14, 4, 43 )
****** 2.371397 s ******
请按任意键继续. . . 确实很快
GMP的二进制内核的输出太慢了
导致过滤函数成为瓶颈