p^2=a^2&b^2

gxqcn

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

无心人

1. 
   
2. #include <gmp.h>
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. 
   
6. mpz_t t;
   
7. unsigned int d[4] = {0, 1, 4, 9}, maxlvl;
   
8. mpz_t l[32];
   
9. 
   
10. int check(int lvl, mpz_t n)
    
11. {
    
12. //    gmp_printf("%Zd\n", n);
    
13. 
    
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. }
    
21. 
    
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.   }
    
49. 
    
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>
   
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. 
   
10. int main(int argc, char* argv[])
    
11. {
    
12.     // 初始化
    
13.     HugeCalc::EnableTimer( TRUE );
    
14.     HugeCalc::ResetTimer();
    
15. 
    
16.     // (9_k)7 ^ 2 = (9_k)4(0_k)9  (k>=1)
    
17.     CHugeInt hBase( 97 ), hSquare;
    
18. 
    
19.     UINT32 k=1;
    
20. 
    
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.         }
    
29.         
    
30.         hBase.DecLShift(1) += 27;
    
31.     } while ( ++k <= 1024 );
    
32. 
    
33.     HugeCalc::EnableTimer( FALSE );
    
34. 
    
35.     printf( "\n" );
    
36. 
    
37.     system( "pause" );
    
38. 
    
39.     return 0;
    
40. }

复制代码

运行结果为：

1. 
   
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 的一个解。