平方素数问题

mathe

我也来个素数话题吧。 我们知道不存在完全平方数同时是素数。 那么如果将两个完全平方数连接起来如何呢？ 比如11,19都是由两个完全平方数连接而成的素数。我们将这种素数称为平方素数吧。 此外，如果两个平方数的位数相同，我们可以称为均匀平方素数。 如果交换两个平方数的位置结果还是素数，就称为对偶平方素数，如149和491 请分别在一定范围求出所有的平方素数，均匀平方素数和对偶平方素数（范围自定吧，比如10^19?)

无心人

那可参与的平方数字就少多啦

medie2005

平方素数太多，估计10^19以内不会少于1亿个。 10^10以内的平方素数表：

mathe

你是自己算出来的？将程序贴出来看看。 平方素数应该会很多。但是后面几个变种应该少很多

medie2005

直接穷举，未做筛选。 #include #include #include using namespace std; __int64 TEMP=65536, Limit=TEMP*TEMP/2; const int L=10; __int64 POWOF10[L], Max; void Perpare( ){ POWOF10[0]=1; Max=10; for( int i=1; i0 ){ if( (b&1) && (r=r+t)>mod ) r-=mod; if( (t<<=1)>mod ) t-=mod; b>>=1; } return r; } __int64 PowModular( __int64 base, __int64 n, __int64 mod ){ __int64 s=1, t=base, u=n; while(u){ if(u&1) s=(s>=Limit || t>=Limit)? MultiModular( s, t, mod ) : (s*t)%mod; u>>=1; t=(t>=Limit)? MultiModular( t, t, mod ) : (t*t)%mod; } return s; } bool Miller_Rabin_Test( __int64 n ){ int base[]={2,3,7,61,24251},base_num=sizeof(base)/sizeof(base[0]); __int64 t=n-1; int s=0; while( (t&1)==0 ) t>>=1, ++s; for( int i=0; i=Limit)? MultiModular( r, r, n ) : (r*r)%n; } if( jPOWOF10[k2] ) ++k2, E*=10; T=Temp2+E; } Temp1+=(i<<1)+2; ++i; if( Temp1>POWOF10[k1] ) ++k1; } file<

gxqcn

原帖由 medie2005 于 2008-4-8 16:55 发表 ... #bool Miller_Rabin_Test( __int64 n ){ int base[]={2,3,7,61,24251} ...

上面的测试基可以保证 $10^16$ 内除了 46,856,248,255,981 外不会发生误判（注：HugeCalc 中也利用了该结论）。 具体可参见：http://math.crg4.com/primes.html

无心人

还有这个好处？ 不知道混合用Miller-rabin测试和lucas测试各10次会有多少概率遇到合数？

manthanein

http://oeis.org/A167535