p^2=a^2&b^2

gxqcn

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

无心人

2. #include <gmp.h>
3. #include <stdio.h>
4. #include <stdlib.h>
6. mpz_t t;
7. unsigned int d[4] = {0, 1, 4, 9}, maxlvl;
8. mpz_t l[32];
10. int check(int lvl, mpz_t n)
11. {
12. // gmp_printf("%Zd\n", n);
14. if (mpz_perfect_square_p(n))
15. {
16. mpz_sqrt(t, n);
17. if (mpz_probab_prime_p(t, 10) > 0)
18. gmp_printf("%u: [%Zd, %Zd]\n", lvl, n, t);
19. }
20. }
22. int circle(int lvl)
23. {
24. if (lvl < maxlvl)
25. for (int i = 0; i < 4; i ++ )
26. {
27. mpz_mul_ui(l[lvl], l[lvl-1], 10);
28. mpz_add_ui(l[lvl], l[lvl], d[i]);
29. check(lvl+1, l[lvl]);
30. circle(lvl + 1);
31. }
32. }
33. int main(void)
34. {
35. int i;
36. mpz_init(t);
37. for (i = 0; i < 32; i ++)
38. {
39. mpz_init(l[i]);
40. mpz_set_ui(l[i], 0);
41. }
42. printf("请输入最大数字长度：");
43. scanf("%u", &maxlvl);
44. for (i = 1; i < 4; i ++)
45. {
46. mpz_set_ui(l[0], d[i]);
47. circle(1);
48. }
50. for (i = 0; i < 32; i ++)
51. mpz_clear(l[i]);
52. mpz_clear(t);
53. return 0;
54. }

复制代码

先程序代码奉上

无心人

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

gxqcn

原帖由 无心人 于 2009-3-24 16:37 发表 gxq 有没有大幅度减枝的算法

没及细想。 但粗略读了你的代码，不知下面两点你用上没有？ 一、末尾需1或9； 二、数字总和不被3整除，也即 1的个数 + 4的个数 总和不被 3 整除。 当然，这是将目标锁定在素数的平方前提上。

无心人

9: [100140049, 10007] 13: [1004499049009, 1002247] 11: [10110101401, 100549] 15: [101914011991009, 10095247] 9: [104919049, 10243] 7: [1100401, 1049] 14: [11004194004049, 3317257] 14: [11199109101049, 3346507] 5: [11449, 107] 13: [1144944940441, 1070021] 12: [144019491001, 379499] 11: [41110401049, 202757] 9: [414000409, 20347] 15: [419041411191001, 20470501] 15: [444999910990441, 21095021] 2: [49, 7] 12: [490001400001, 700001] 10: [4900140001, 70001] 8: [49014001, 7001] 15: [490400094910441, 22144979] 6: [491401, 701] 16: [9010901999944441, 94925771] 14: [90940044990001, 9536249] 4: [9409, 97] 10: [9409194001, 97001] 11: [94094949001, 306749] 6: [994009, 997] 14: [99400919940001, 9970001] 12: [994010994001, 997001] 好了，再加上 1: [4,2] 1: [9,3] 16位内的带0的结果出来了

无心人

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

gxqcn

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

无心人

我想他gmp库里的判断平方数的函数应该利用了某些规则 据说判定63, 64, 65等几个数字的剩余就能淘汰95%以上 不知道他利用了么 我看他代码去 如果利用了 我想，并不需要再额外处理了

无心人

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

gxqcn

又有一个规律可用：(9_k)7 ^ 2 = (9_k)4(0_k)9 (k>=1) 编代码如下：

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" )
10. int main(int argc, char* argv[])
11. {
12. // 初始化
13. HugeCalc::EnableTimer( TRUE );
14. HugeCalc::ResetTimer();
16. // (9_k)7 ^ 2 = (9_k)4(0_k)9 (k>=1)
17. CHugeInt hBase( 97 ), hSquare;
19. UINT32 k=1;
21. do
22. {
23. if ( hBase.IsPrime() )
24. {
25. printf( "\n%s\tk=%u\t", HugeCalc::GetTimerStr( FT_DOT06SEC_s ), k );
26. // printf( "%s ^ 2 = ", (LPCTSTR)hBase );
27. // printf( "%s", (LPCTSTR)hSquare.Pow( hBase, 2 ) );
28. }
30. hBase.DecLShift(1) += 27;
31. } while ( ++k <= 1024 );
33. HugeCalc::EnableTimer( FALSE );
35. printf( "\n" );
37. system( "pause" );
39. return 0;
40. }

复制代码

运行结果为：

2. 0.000011 s k=1
3. 0.000085 s k=2
4. 0.000627 s k=16
5. 0.069882 s k=139
6. 13.765550 s k=989
7. 请按任意键继续. . .

复制代码

如 k=16 时， 99999999999999997 ^ 2 = 9999999999999999400000000000000009 也可看作 Q3/Q4 的一个解。