平方素数问题
我也来个素数话题吧。我们知道不存在完全平方数同时是素数。
那么如果将两个完全平方数连接起来如何呢？
比如11,19都是由两个完全平方数连接而成的素数。我们将这种素数称为平方素数吧。
此外，如果两个平方数的位数相同，我们可以称为均匀平方素数。
如果交换两个平方数的位置结果还是素数，就称为对偶平方素数，如149和491
请分别在一定范围求出所有的平方素数，均匀平方素数和对偶平方素数（范围自定吧，比如10^19?) 那可参与的平方数字就少多啦 平方素数太多，估计10^19以内不会少于1亿个。
10^10以内的平方素数表： 你是自己算出来的？将程序贴出来看看。
平方素数应该会很多。但是后面几个变种应该少很多 直接穷举，未做筛选。
#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
__int64 TEMP=65536, Limit=TEMP*TEMP/2;
const int L=10;
__int64 POWOF10, Max;
void Perpare( ){
POWOF10=1; Max=10;
for( int i=1; i<L; ++i )
Max*=10, POWOF10=POWOF10*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;
}
__int64PowModular( __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;
}
boolMiller_Rabin_Test( __int64 n ){
int base[]={2,3,7,61,24251},base_num=sizeof(base)/sizeof(base);
__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 )return true;
__int64 r=PowModular( base, 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, 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, E*=10;
T=Temp2+E;
}
Temp1+=(i<<1)+2;
++i;
if( Temp1>POWOF10 )
++k1;
}
file<<count<<endl;
system("PAUSE");
return EXIT_SUCCESS;
} 原帖由 medie2005 于 2008-4-8 16:55 发表 http://images.5d6d.net/dz60/common/back.gif
...
#boolMiller_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次会有多少概率遇到合数？ http://oeis.org/A167535
页:
[1]