mathe 发表于 2008-4-3 17:41:47

平方素数问题

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

无心人 发表于 2008-4-3 19:57:17

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

medie2005 发表于 2008-4-8 15:05:28

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

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

mathe 发表于 2008-4-8 16:16:27

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

medie2005 发表于 2008-4-8 16:55:45

直接穷举,未做筛选。

#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;
}

gxqcn 发表于 2008-4-8 18:43:32

原帖由 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

无心人 发表于 2008-4-8 20:07:50

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

manthanein 发表于 2017-1-30 18:03:09

http://oeis.org/A167535
页: [1]
查看完整版本: 平方素数问题