p^2=a^2&b^2 - 第3页 - 算法交流 - 数学研发论坛

gxqcn 发表于 2009-3-24 16:34:40

这类问题，若用暴力穷举，那就仅拼机器性能或运气了，
而这两样我都不具备，所以不敢尝试。。。:lol :lol :lol

无心人 发表于 2009-3-24 16:35:24

#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>

mpz_t t;
unsigned int d = {0, 1, 4, 9}, maxlvl;
mpz_t l;

int check(int lvl, mpz_t n)
{
// gmp_printf("%Zd\n", n);

if (mpz_perfect_square_p(n))
{
   mpz_sqrt(t, n);
   if (mpz_probab_prime_p(t, 10) > 0)
      gmp_printf("%u: [%Zd, %Zd]\n", lvl, n, t);
}
}

int circle(int lvl)
{
if (lvl < maxlvl)
for (int i = 0; i < 4; i ++ )
   {
      mpz_mul_ui(l, l, 10);
      mpz_add_ui(l, l, d);
      check(lvl+1, l);
      circle(lvl + 1);
   }
}
int main(void)
{
int i;
mpz_init(t);
for (i = 0; i < 32; i ++)
{
mpz_init(l);
mpz_set_ui(l, 0);
}
printf("请输入最大数字长度：");
scanf("%u", &maxlvl);
for (i = 1; i < 4; i ++)
{
mpz_set_ui(l, d);
circle(1);
}

for (i = 0; i < 32; i ++)
mpz_clear(l);
mpz_clear(t);
return 0;
}
先程序代码奉上

无心人 发表于 2009-3-24 16:37:06

gxq 有没有大幅度减枝的算法

gxqcn 发表于 2009-3-24 16:41:43

原帖由无心人于 2009-3-24 16:37 发表 http://bbs.emath.ac.cn/images/common/back.gif
gxq 有没有大幅度减枝的算法

没及细想。

但粗略读了你的代码，不知下面两点你用上没有？
一、末尾需1或9；
二、数字总和不被3整除，也即 1的个数 + 4的个数总和不被 3 整除。

当然，这是将目标锁定在素数的平方前提上。

无心人 发表于 2009-3-24 16:42:29

9:
13:
11:
15:
9:
7:
14:
14:
5:
13:
12:
11:
9:
15:
15:
2:
12:
10:
8:
15:
6:
16:
14:
4:
10:
11:
6:
14:
12:

好了，再加上
1:
1:
16位内的带0的结果出来了

无心人 发表于 2009-3-24 16:43:37

TO GxQ
你这两个都不能加
除非是求固定位数的啊

gxqcn 发表于 2009-3-24 16:46:02

不会吧？

那你可以从数字头部添加数字啊？

无心人 发表于 2009-3-24 16:54:02

:)

我想他gmp库里的判断平方数的函数应该利用了某些规则
据说判定63, 64, 65等几个数字的剩余就能淘汰95%以上
不知道他利用了么

我看他代码去

如果利用了
我想，并不需要再额外处理了

无心人 发表于 2009-3-24 17:04:06

:(

看不懂
算了，不纠缠这个题目了

gxqcn 发表于 2009-3-24 17:11:07

另一个构造法

又有一个规律可用：(9k)7 ^ 2 = (9k)4(0k)9(k>=1)

编代码如下：#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" )

int main(int argc, char* argv[])
{
// 初始化
HugeCalc::EnableTimer( TRUE );
HugeCalc::ResetTimer();

// (9_k)7 ^ 2 = (9_k)4(0_k)9(k>=1)
CHugeInt hBase( 97 ), hSquare;

UINT32 k=1;

do
{
   if ( hBase.IsPrime() )
   {
         printf( "\n%s\tk=%u\t", HugeCalc::GetTimerStr( FT_DOT06SEC_s ), k );
//       printf( "%s ^ 2 = ", (LPCTSTR)hBase );
//       printf( "%s", (LPCTSTR)hSquare.Pow( hBase, 2 ) );
   }

   hBase.DecLShift(1) += 27;
} while ( ++k <= 1024 );

HugeCalc::EnableTimer( FALSE );

printf( "\n" );

system( "pause" );

return 0;
}运行结果为：
0.000011 s    k=1
0.000085 s    k=2
0.000627 s    k=16
0.069882 s    k=139
13.765550 s k=989
请按任意键继续. . .如 k=16 时，
99999999999999997 ^ 2 = 9999999999999999400000000000000009
也可看作 Q3/Q4 的一个解。:)

页: 1 2 [3] 4

数学研发论坛's Archiver

另一个构造法