UC知道求费尔马二平方素数
来源：百度知道 编辑：UC知道 时间：2024/06/21 23:01:49
?例如：?5=1-1+2*213=2*2+3*3?17=1*1+4*4 29=2*2+5*5?这就是著名的费尔马“二平方”定理。有趣的是：上述等式右侧的数有的又恰恰是两个素数的平方，如13,29的表达式，我们起名叫作费尔马“二平方”素数，即如果一个素数能够表示成两个素数的平方和的形式：?F＝X＊X＋Y ＊Y （1）?其中F、X、Y 都是素数，它就是费尔马“二平方”素数。
贴一段给你：
编程思路?本文拟用c 语言编程，求42亿之内的费尔马“二平方”素数。?如果按定义从左向右，先求一个素数F，然后再去找相应的素数X、Y ，工作量重复太大。我们可以对上述公式进行分析：
?1、左侧F 是素数，它肯定是奇数，那么右侧两式的和也应该是奇数，这样X 和Y 为一奇一偶，因为奇数的平方还是奇数，偶数的平方还是偶数。X、Y 又要求是素数，而既是偶数又是素数的数只有一个，就是2。我们假定X＝2。所以（1）式可以简化为：?F＝2＊2＋Y ＊Y（2）?也就是说，费尔马“二平方”素数的表示形式是惟一的。
?2、按式（2）由右向左，由小到大找素数Y ，再计算出相应的F，判断其是否素数。
?3、求出素数Y 后将其保存起来，在判断其它数是否素数时可直接用已求出的素数去除，如此反复。
?源程序?
#include<math.h>?
void main()
{
unsigned long i,j,a[10000],m,m1=3,m2=7,b=1,n=0,d=1,x=4000000000;?
a[1]=2;?
10:for(i=m1;i<=m2;i++,i++)?
{
if(i%a[1]==0) goto 13;
for(j=2;j<=d-1;j++)?
if(i%a[j]==0) goto 13;?
a[b++]=i; m=i*i+4;?
if(m>x) goto 14;?
for(j=2;j<=b-2;j++)?
if(m%a[j]==0) goto 13;?
printf("%20lu=2*2+%5lu*%5lu",m,i,i);?
if(++n%2==0) printf("\n");?
13:m1=m2+4; m2=a[++d]*a[d]-2;?
goto 10;?
14:printf("\ntota