平方逆素数

无心人

考虑对称的逆素数181 16361
如果把从中间开始到各位的数字拿出来
81 361是个平方数
我们称这种数叫平方逆素数
现在求出16位以内的平方逆素数

同样的我们也有从最高位到中间位是平方数的数字
即818, 36163
那么这种情况下是否也存在平方逆素数呢？

winxos

考虑对称的逆素数181 16361
如果把从中间开始到各位的数字拿出来
81 361是个平方数
-----------------------
没看明白,什么叫从中间开始到各位？怎么又拿出了81361？

medie2005

181,  16361
这是两个数.前一个数对应81,后一个对应361.

winxos

哦原来是这样啊！
那可以先求得10^8以内的平方数，
然后对所有数对称变换得到该类数，再判断素性。

winxos

181
       16361
     9801089
     1062601
     1273721
     9657569
     9049409
   944111449
   986313689
   921515129
   184636481
   104040401
   963545369
   186484681
   902888209
这是十位以内的，更大点也差不多，因为平方后的数不很多。

无心人

更大的是考验快速淘汰的

winxos

那应该可以在平方完后的数就先进行一轮的淘汰，
具体的淘汰方法要慢慢思考。

无心人

Haskell代码
求的是10^8内的平方组成的素数

Prelude Primes> let inv n = snd \$ until (\(x, y) -> x==0) (\(x,y) -> (div x 10, (mod x 10) + y * 10)) (n, 0)
Prelude Primes> let l10 n = snd \$ until (\(x, y) -> x == 0) (\(x, y)->(div x 10, y+1)) (n, 0)
Prelude Primes> let aa = [n | x <- [1..9999], let s = x*x, let invs = inv s, let l = l10 s, let n = (div invs 10) * 10^l + s, isPrime n]

结果是：
Prelude Primes> aa
[181,16361,9801089,1062601,1273721,9657569,9049409,944111449,986313689,921515129
,184636481,104040401,963545369,186484681,902888209,18261116281,10232123201,10806
160801,16557175561,92328182329,96909190969,90250205209,96388288369,94849294849,9
4201310249,14062326041,98893339889,12964346921,16138383161,98844444889,929254529
29,98466466489,96917471969,12550505521,14860606841,90844644809,18445654481,12930
703921,94601710649,90471717409,10802720801,90672727609,96768786769,90451815409,9
8407870489,14485958441,98266966289,90049994009,1259701079521,1863801083681,10640
11104601,1658611168561,1022121212201,1237921297321,9049231329409,1421731371241,1
215351535121,1800451540081,9428071708249,1278171718721,9230571750329,14610919016
41,1027591957201,1082691962801,1254312134521,1447812187441,1803222223081,1065042
405601,1659942499561,9658152518569,9467352537649,9864162614689,9842382832489,121
4203024121,9484123214849,1279723279721,1425433345241,9654733374569,9063343433609
,9213253523129,9002104012009,9408204028049,1636704076361,9252904092529,169421412
4961,9020914190209,1066024206601,9842724272489,1422234322241,1293634363921,94608
34380649,9047934397409,1610944490161,9658764678569,9023584853209,9259594959529,1
447515157441,9422235322249,9699435349969,9862065602689,1469565659641,98256161652
89,1805926295081,1445536355441,9806146416089,9636346436369,1047946497401,9698656
568969,9652966692569,9065776775609,1469686869641,9211096901129,1461196911641,965
1907091569,1424317134241,9274147414729,9256347436529,9401067601049,1482277722841
,1670958590761,9002898982009,9618709078169,1696819186961,9633229223369,944356965
3449,1613089803161,1291999991921,948482010284849,982254010452289,900345010543009
,121436010634121,980877010778089,182261111162281,108512111215801,967903111309769
,146363111363641,986444111444689,104909111909401,144301212103441,121371212173121
,940102212201049,100752212257001,940992212299049,963015212510369,948255212552849
,906189212981609,921551313155129,144022414220441,980113414311089,127325414523721
,129737414737921,161969414969161,100299515992001,963792616297369,184574616475481
,140375616573041,965307616703569,129917616719921,946257616752649,904587616785409
,123131717131321,942185717581249,148618717816841,925768717867529,940300818003049
,900730818037009,982702818207289,163422818224361,144142818241441,921321919123129
,986012919210689,129654919456921,963819919918369,900322020223009,180133020331081
,186359222953681,902235424532209,186195424591681,940070525070049,163091525190361
,923537525735329,123904626409321,165817626718561,180864727468081,188260929062881
,104317929713401,963448929844369,169909929909961,144184030481441,963856030658369
,906393131393609,986055131550689,182420232024281,963836232638369,163448232844361
,980344333443089,106156333651601,161544434445161,921294434492129,127172535271721
,104414535414401,929929636929929,161985737589161,946809737908649,129759737957921
,908204838402809,927527838725729,982058838850289,180571939175081,125155939551521
,165180040081561,904482040284409,944114040411449,108279040972801,125447141744521
,963077141770369,148726242627841,106519242915601,902039444930209,125730545037521
,169441545144961,100945545549001,121117545711121,165266646662561,102639646936201
,188540747045881,146023747320641,161843747348161,165278747872561,940890949098049
,925223949322529,125745949547521,902066949660209,167079949970761,944905050509449
,967639050936769,948781353187849,923626353626329,144539555935441,180583656385081
,188483858384881,906674858476609,904865858568409,142448858844241,948793959397849
,169345060543961,948037060730849,127110161011721,923991161199329,146259161952641
,123632262236321,104812363218401,100489363984001,982272464272289,186756464657681
,921389565983129,146080666080641,908091767190809,925386767683529,961848767848169
,121188767881121,925244868442529,929833969338929,129835969538921,188804070408881
,969281171182969,963226171622369,927197171791729,925958171859529,144398171893441
,180790272097081,100762272267001,144706272607441,969423373324969,944080474080449
,967381474183769,967795474597769,906077474770609,140523575325041,984493575394489
,969364575463969,104707575707401,963619575916369,927090676090729,925061676160529
,144591676195441,121073676370121,940044676440049,900015676510009,100545676545001
,982068676860289,144039676930441,927530777035729,148070777070841,963112777211369
,184895777598481,923548777845329,142159777951241,129721878127921,946891878198649
,986326878623689,146496878694641,921037878730129,904362979263409,182073979370281
,969968979869969,125307181703521,986911383119689,144946090649441,106122191221601
,965019191910569,129849191948921,108041292140801,921206292602129,948522494225849
,121848494848121,929965696569929,904369696963409,946841898148649,106289898982601
,180028999820081,900049999940009]

无心人

另外一种形式的结果
Prelude Primes> let bb = [n | x <- [1..9999], let s = x*x, let invs = inv s, let l = l10 s, let n = s * 10^(l-1) + mod invs (10^(l-1)), isPrime n]
Prelude Primes> bb
[32423,78487,1444441,1600061,1764671,1936391,3364633,3721273,9604069,9801089,104
040401,110252011,114494411,116646611,118818811,141616141,176898671,193212391,196
000691,353444353,357212753,361000163,380252083,734414437,767292767,961000169,992
252299,998565899,10176167101,10824142801,10956165901,11155655111,11424442411,118
33633811,12180108121,13838483831,14288488241,14592429541,15054445051,15920102951
,16321612361,16728182761,17305650371,18748984781,18922522981,19184448191,1953646
3591,30030403003,30360106303,30802520803,31584448513,33292929233,33640004633,338
72427833,34574447543,34692129643,35760406753,35880108853,36481618463,37332123373
,37945654973,38068986083,38440004483,71233633217,72760906727,73102520137,7361646
1637,74476967447,75864146857,76038483067,79032123097,90440104409,93896169839,940
90009049,95257675259,95452925459,96040004069,97812121879,99600400699,10221212122
01,1056784876501,1077444447701,1098304038901,1149184819411,1151329231511,1261129
211621,1317904097131,1322500052231,1364224224631,1394761674931,1416100016141,142
0864680241,1473796973741,1488400048841,1517824287151,1560001000651,1577536357751
,1585081805851,1617984897161,1620529250261,1630729270361,1708249428071,171872127
8171,1752976792571,1774224224771,1827904097281,1863225223681,1885129215881,19293
21239291,1932100012391,1940449440491,1948816188491,1957201027591,1960000000691,1
962801082691,3003289823003,3083536353803,3139984899313,3164841484613,32688646886
23,3352561652533,3363556553633,3426201026243,3429904099243,3463321233643,3538161
618353,3610000000163,3613801083163,3678724278763,3732624262373,3751969691573,384
5521255483,3849444449483,3865156515683,3892729272983,3960100010693,3968064608693
,3972049402793,7064964694607,7166329236617,7209225229027,7295401045927,740384148
3047,7573504053757,7612081802167,7656289826567,7772944492777,7862416142687,79298
56589297,9048064608409,9078169618709,9174841484719,9265936395629,9296401046929,9
302500052039,9406489846049,9455625265549,9461776771649,9467929297649,96038010830
69,9641025201469,9672100012769,9740641460479,9859600069589,9991921291999,1002988
98892001,101060414060101,101888646888101,103619616916301,103812848218301,1041998
48991401,104393616393401,106015363510601,106341212143601,106863616368601,1084384
94834801,108966010669801,109825969528901,110356848653011,110622767226011,1111555
65551111,111355696553111,111422444224111,111489212984111,111556000655111,1119571
61759111,112292010292211,113771292177311,114176414671411,114853212358411,1150566
46650511,115464040464511,115532010235511,116144646441611,117923565329711,1188870
40788811,119646818646911,119854444458911,119992969299911,120270242072021,1204784
14874021,120825767528021,121034414430121,121243242342121,122360040063221,1233414
44143321,124256252652421,125174444471521,126380252083621,126451363154621,1275204
14025721,128952818259821,129744040447921,130465444564031,131478767874131,1322776
96772231,132860252068231,133809646908331,134835848538431,134982767289431,1353504
14053531,136456363654631,137122090221731,137196161691731,137344363443731,1383096
16903831,138979848979831,139129000921931,139278242872931,140475040574041,1419782
42879141,142581767185241,143868494868341,145084818480541,145694898496541,1460004
14000641,147609646906741,148379040973841,149227696722941,150388848883051,1505440
00445051,151788161887151,152256040652251,154134767431451,154291848192451,1554724
94274551,155788090887551,156183040381651,158165292561851,159121212121951,1606406
46046061,160720818027061,160881212188061,161764848467161,162570242075261,1628929
69298261,164187040781461,165486242684561,167526494625761,167690252096761,1677721
61277761,169496898694961,170321292123071,170651616156071,171230444032171,1728064
94608271,174891242198471,175309696903571,177072646270771,177662252266771,1802002
52002081,180455040554081,180625000526081,182158242851281,183355242553381,1836979
69796381,184126818621481,186710414017681,187229292922781,187402414204781,1876622
42266781,188269212962881,189138010831981,191056414650191,191231292132191,1929844
94489291,193160252061391,195364000463591,195540848045591,197491363194791,1977580
90857791,198470252074891,198737646737891,198916000619891,199630242036991,3000848
48480003,300632898236003,302610010016203,303270494072303,304483242384403,3054772
92774503,306694444496603,309580969085903,314496646694413,316068848860613,3164062
52604613,316856414658613,317306898603713,318208818802813,319790252097913,3199033
63309913,320356000653023,323078565870323,323192252291323,327412848214723,3287875
65787823,329476000674923,329590818095923,330050252050033,330165161561033,3328136
16318233,334199616991433,335472646274533,335704363407533,337096363690733,3372124
94212733,337444818444733,338840414048833,340122242221043,344921292129443,3477460
90647743,348100000001843,354025000520453,355216000612553,355573696375553,3582022
52202853,361681969186163,368449000944863,368570414075863,368691848196863,3689347
67439863,369785616587963,370028898820073,372466090664273,373198818891373,3746664
14666473,375891616198573,377118818811773,377979040979773,378471040174873,3809358
48539083,382418565814283,384772090277483,385516818615583,386759616957683,3882536
16352883,390250090052093,390375040573093,390625000526093,390875040578093,3918760
00678193,394258414852493,395012252210593,395515212515593,396648040846693,3974041
61404793,398161000161893,399171242171993,702411616114207,702914565419207,7039210
00129307,704424494424407,706944646449607,707785696587707,708122252221807,7113235
65323117,715885212588517,716900898009617,717578414875717,718256252652817,7189344
14439817,722160040061227,722670010076227,723350252053327,726585767585627,7284622
52264827,729486818684927,731709161907137,732222494222237,733592252295337,7368505
65058637,738052818250837,739084090480937,739600000006937,742009969900247,7428716
16178247,744251292152447,749263363362947,750475696574057,754987212789457,7638760
00678367,764050818050467,764225646522467,765450010054567,766675363576667,7670256
46520767,769655292556967,769830767038967,771059616950177,771937969739177,7752802
52082577,780925696529087,781456000654187,783579040975387,788899242998887,7906766
46676097,790854494458097,791210252012197,791388161883197,791566090665197,7954856
16584597,797627616726797,798878444878897,799951363159997,900411212114009,9009806
46089009,904210818012409,907446767644709,908399616993809,910879363978019,9133624
94263319,914127212721419,916614767416619,917189292981719,917572414275719,9179556
16559719,923328818823329,924482252284429,926598767895629,928139565931829,9289104
44019829,929874494478929,930839040938039,931418010814139,931611040116139,9327696
46967239,936056252650639,936830414038639,940900000009049,941870252078149,9422584
94852249,943423696324349,947118242811749,947312898213749,951990494099159,9527712
12177259,953552252255359,954919848919459,956092848290659,956679616976659,9637348
98437369,969634090436969,974563848365479,975551292155579,976144000441679,9775276
96725779,977725444527779,979704040407979,980298010892089,981684646486189,9820810
00180289,983865616568389,984659292956489,985254767452589,987638444836789,9884336
46334889,999400090004999]

suan1024

1. //求N以内的立方逆素数
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. #include <gmp.h>
   
6. #include "my_data.h"
   
7. 
   
8. char * new_str(char *, const char *);
   
9. char * new_str2(char *, const char *);
   
10. 
    
11. int main()
    
12. {
    
13.     int n,t,c = 0;
    
14.     mpz_t val;   
    
15.     char * str1 = malloc(sizeof(char)*64);  
    
16.     char * str2 = malloc(sizeof(char)*128);  
    
17.     mpz_init(val);      
    
18.     for (n = 3; n < __1d4; n+=1)
    
19.     {        
    
20.         mpz_set_ui(val,n*n);
    
21.         mpz_mul_ui(val,val,n);        
    
22.         str1 = mpz_get_str(str1,10,val);
    
23.         //str2 = new_str(str2,str1);
    
24.         str2 = new_str2(str2,str1);  
    
25.         mpz_set_str(val,str2,10);
    
26.         t = mpz_probab_prime_p(val,10);
    
27.         if (t == 1)
    
28.         {            
    
29.             gmp_printf("[可能的] %d = %Zd\n",n,val);
    
30.             c++;        
    
31.         }
    
32.         else if (t == 2)
    
33.         {
    
34.             gmp_printf("[确定的] %d = %Zd\n",n,val);
    
35.             c++;   
    
36.         }         
    
37.     }      
    
38.     printf(" 立方逆素数 共计 %ld\n",c);
    
39.    
    
40.     free(str1); free(str2);
    
41.     mpz_clear(val);
    
42.    
    
43.     system("AUSE");
    
44.     return 0;
    
45. }
    
46. 
    
47. char * new_str(char * str2, const char * str1)
    
48. {
    
49.      int len1 = strlen(str1);
    
50.      int len2 = (len1 << 1) - 1;     
    
51.      if (str2 == NULL)
    
52.          str2 = malloc(len2+1);      
    
53.      int i,j;
    
54.      for (i = 0; i < len1; i++)
    
55.          str2 = str1[len1-1-i];
    
56.      for (j = 1; j < len1; j++,i++)
    
57.          str2 = str1[j];
    
58.      str2 = '\0';
    
59.      return str2;
    
60. }
    
61. 
    
62. char * new_str2(char * str2, const char * str1)
    
63. {
    
64.      int len1 = strlen(str1);
    
65.      int len2 = (len1 << 1) - 1;     
    
66.      if (str2 == NULL)
    
67.          str2 = malloc(len2+1);      
    
68.      int i,j;
    
69.      for (i = 0; i < len1; i++)
    
70.          str2 = str1;   
    
71.      for (j = 1; j < len1; j++,i++)
    
72.          str2 = str1[len1-j-1];
    
73.      str2 = '\0';
    
74.      return str2;
    
75. }

复制代码