平方逆素数

无心人

考虑对称的逆素数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"
8. char * new_str(char *, const char *);
9. char * new_str2(char *, const char *);
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);
40. free(str1); free(str2);
41. mpz_clear(val);
43. system("AUSE");
44. return 0;
45. }
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. }
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. }

复制代码