平方素数问题

mathe

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

无心人

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

medie2005

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

10^10以内的平方素数表：

mathe

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

medie2005

直接穷举，未做筛选。

#include <cstdlib>
#include <iostream>
#include <fstream>
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; i<L; ++i )
  Max*=10, POWOF10[i]=POWOF10[i-1]*10;
}
__int64 MultiModular( __int64 a, __int64 b, __int64 mod ){
__int64 r=0, t=a%mod;
while( b>0 ){
  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<base_num; ++i ){
  if( n==base[i] )  return true;
  __int64 r=PowModular( base[i], t, n );
  if( r==1 ) continue;
  int j;
  for( j=0; j<s; ++j ){
   if( r==n-1 ) break;
   r=(r>=Limit)? MultiModular( r, r, n ) : (r*r)%n;
  }
  if( j<s ) continue;
  return false;
}
return true;
}
int main()
{
    ofstream file("output.txt");
    int count=0;
Perpare( );
for( __int64 i=1, k1=1, Temp1=1; Temp1<Max; ){
  for( __int64 j=1, k2=1, E=i*i*POWOF10[k2], Temp2=j*j, T=Temp2+E; T<Max; ){   
   if( Miller_Rabin_Test( T ) )
    file<<T<<endl, ++count;
            Temp2+=(j<<2)+4;  j+=2;
            if( Temp2>POWOF10[k2] )
                ++k2, E*=10;
            T=Temp2+E;                    
  }
  Temp1+=(i<<1)+2;
  ++i;
  if( Temp1>POWOF10[k1] )
      ++k1;
    }
file<<count<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

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