懂C语言和数论的来，高分题，帮我看看程序

Question

目的是设计让一个模四剩一的质数写成两个正整数平方相加的和的形式，比如，5=1*1+2*2,输出的两个数字为1,2，问题是我用费马降价法设计的程序，居然不是全错，也不是全对，正确率大概60%,这是怎么回事，求高手告诉我程序中的问题。
#include<stdio.h>
#include<math.h>
int P(int x)
{
int a,b;
b=(int)sqrt(x);
for(a=2;a<=b;a++)
if(x%a==0)
break;
if(a>b)
return 1;
else
return 0;
}
int r(int a,int b,int c)
{
int d,e,f,g;
e=a%c;
g=1;
for(d=0;d<=b;d++)
{
if(b>=(int)pow(2,d))
continue;
else
{
b=b-(int)pow(2,d-1);
for(f=1;f<=d-1;f++)
{
e=((int)pow(e,2))%c;
}
d=0;
}
g=(e*g)%c;
e=a%c;
}
return (g);
}
int ZXYG(int c)
{
int a,b,d,e,f,g;
if(P(c)==1)
for(a=2;a<=c-1;a++)
{
for(b=1;b<=c-1;b++)
{
if(r(a,b,c)==1)
break;
else
continue;
}
if(b==c-1)
break;
else
continue;
}
return (a);
}
int I(int a,int b)
{
int c,d,e;
c=ZXYG(b);
for(d=1;d<=b-1;d++)
{
e=r(c,d,b);
if(e==a)
break;
else
continue;
}
return (d);
}
int zxj(int a,int b,int c,int d)
{
int e,f;
for(e=1;e<=d-1;e++)
{
if((I(a,d)+b*e-I(c,d))%(d-1)==0)
for(f=1;f<=d-1;f++)
{
if(I(f,d)==e)
break;
else
continue;
}
else
continue;
if(I(f,d)==e)
break;
else
continue;
}
if(f>(d/2))
f=d-f;
return f;
}
void main()
{
int p,a,b,u,v,r,c,d,M
scanf("%d",&p);
if((P(p)==1)&&(p%4==1))
{
b=1;
a=zxj(1,2,p-1,p);
M=(a*a+b*b)/p;
while(M!=1)
{
u=a%M;
if(u>M/2)
u=0-u;
v=b%M;
if(v>M/2)
v=0-v;
r=(u*u+v*v)/M;
c=(a*u+v*b)/M;
d=(a*v-u*b)/M;
a=c;
b=d;
if(a<0)
a=0-a;
if(b<0)
b=0-b;
M=r;
}
printf("%d,%d",a,b);
}
}
目前89是运算错误的，157会停止工作，就是说有些数字没法操作，一般还是对的。为什么89会运算成1的平方加12的平方（正确的是5的平方加8的平方）.
步骤是（判断质数函数就不解释了）先定义一个a的b次方除c所得余数的函数，其次定义一个寻找最小原根（费马小定理a若小于质数p，a的p-1次方除p余一，原根g指的是g至少要p-1次方才能除p余1）的函数，后是定义指数坐标，求出原根多少次方余质数p得到a，接着是定义函数解同余方程。之后解方程x平方同余p－1模p（p是模4剩1的质数才有解，这个这里不证明），得到x，x、1就为a，b的初值，a的平方加b的平方除以p得到整数M。后求a同余u模M，b同余v同余M，若余数大于M／2,就用余数减去M得到负余数，后u的平方加v的平方除以M得到整数r。用式子（A*A+B*B)(U*U+V*V)=(A*U+B*V)^2+（A*V-B*U)^2＝M^2*rp的等式得新的等式（（A*U+B*V)／m）^2+（（A*V-B*U)^2／m）＾2＝rp，然后把r做M，两个平方项的整数作为a，b重新带入等式运算，直到M＝1，就有了p＝a＾2＋b＾2这种东西了。

Answer 1

#include<stdio.h>
#include<math.h>
int P(int x)
{
int a,b;
b=(int)sqrt(x);
for(a=2;a<=b;a++)
if(x%a==0)
break;
if(a>b)
return 1;
else
return 0;
}
int r(int a,int b,int c)
{
int d,e,f,g;
e=a%c;
g=1;
for(d=0;d<=b;d++)
{
if(b>=(int)pow(2,d))//不要用pow,这个返回的是浮点数,有可能不准确的.
continue;
else
{
b=b-(int)pow(2,d-1);
for(f=1;f<=d-1;f++)
{
e=((int)pow(e,2))%c;
}
d=0;
}
g=(e*g)%c;
e=a%c;
}
return (g);
}
int ZXYG(int c)
{
int a,b,d,e,f,g;
if(P(c)==1)
for(a=2;a<=c-1;a++)
{
for(b=1;b<=c-1;b++)
{
if(r(a,b,c)==1)
break;
else
continue;
}
if(b==c-1)
break;
else
continue;
}
return (a);
}
int I(int a,int b)
{
int c,d,e;
c=ZXYG(b);
for(d=1;d<=b-1;d++)
{
e=r(c,d,b);
if(e==a)
break;
else
continue;
}
return (d);
}
int zxj(int a,int b,int c,int d)
{
int e,f;
for(e=1;e<=d-1;e++)
{
if((I(a,d)+b*e-I(c,d))%(d-1)==0)
for(f=1;f<=d-1;f++)
{
if(I(f,d)==e)
break;
else
continue;
}
else
continue;
if(I(f,d)==e)
break;
else
continue;
}
if(f>(d/2))
f=d-f;
return f;
}
void main()
{
int p,a,b,u,v,r,c,d,M;
scanf("%d",&p);
if((P(p)==1)&&(p%4==1))
{
b=1;
a=zxj(1,2,p-1,p);
M=(a*a+b*b)/p;
while(M!=1)
{
u=a%M;
if(u>M/2)
u=0-u;
v=b%M;
if(v>M/2)
v=0-v;
r=(u*u+v*v)/M;
c=(a*u+v*b)/M;
d=(a*v-u*b)/M;
a=c;
b=d;
if(a<0)
a=0-a;
if(b<0)
b=0-b;
M=r;
}
printf("%d,%d",a,b);
}
}

Answer 2

这是别人写的代码，给你参考一下。

#include <cstdio>

template<typename T>
inline void swap(T& a, T&b)
{
T tmp;
tmp = a;
a = b;
b = tmp;
}

inline int pow_mod(int u, int n, int p)
{
int ret = 1;
for (; n; n >>= 1)
{
if (n&1) ret = (int)u * ret % p;
u = (int)u*u % p;
}
return ret;
}
inline int find(int p)
{
int ret = 2;
for (ret = 2;pow_mod(ret, (p-1) >> 1, p) != p - 1; ++ret);//这里可以改成随机的
return pow_mod(ret, (p-1)>>2, p);
}

int main()
{
for (int caseID = 1, p; scanf("%d", &p) == 1; ++caseID)
{
if ((p&3) != 1) {puts("Illegal");continue;}
int y = 1, x = find(p);
for (int s = x * x + y * y; s != p;)
{
int k = s / p, k2 = k>> 1;
int a = (x % k + k)%k, b = (y % k + k) % k;
if (a > k2) a = k - a;
if (b > k2) b = k - b;
if ((x * a + y * b) % k) swap(a, b);
int u = (x * a + y * b) / k, v = (b * x - a * y) / k;
x = u, y = v;
int t = x * x + y * y;
s = t;
}
if (y < 0) y = -y;
if (x < 0) x = -x;
if (x > y) swap(x, y);
printf("Legal %d %d\n", x, y);
}
return 0;
}

参考资料：http://hi.baidu.com/feixue/blog/item/801bc8fc5916c2f3fc037f8b.html

Answer 3

#include<stdio.h>
#include<math.h>
int P(double x)
{
int a,b;
b=(int)sqrt(x);
for(a=2;a<=b;a++)
if((int)x%a==0)
break;
if(a>b)
return 1;
else
return 0;
}
int r(int a,int b,int c)
{
int d,e,f,g;
e=a%c;
g=1;
for(d=0;d<=b;d++)
{
if(b>=(int)pow(2.0,(double)d))
continue;
else
{
b=b-(int)pow(2.,(double)(d-1));
for(f=1;f<=d-1;f++)
{
e=((int)pow((double)e,2.0))%c;
}
d=0;
}
g=(e*g)%c;
e=a%c;
}
return (g);
}
int ZXYG(int c)
{
int a,b;
if(P(c)==1)
for(a=2;a<=c-1;a++)
{
for(b=1;b<=c-1;b++)
{
if(r(a,b,c)==1)
break;
else
continue;
}
if(b==c-1)
break;
else
continue;
}
return (a);
}
int I(int a,int b)
{
int c,d,e;
c=ZXYG(b);
for(d=1;d<=b-1;d++)
{
e=r(c,d,b);
if(e==a)
break;
else
continue;
}
return (d);
}
int zxj(int a,int b,int c,int d)
{
int e,f;
for(e=1;e<=d-1;e++)
{
if((I(a,d)+b*e-I(c,d))%(d-1)==0)
for(f=1;f<=d-1;f++)
{
if(I(f,d)==e)
break;
else
continue;
}
else
continue;
if(I(f,d)==e)
break;
else
continue;
}
if(f>(d/2))
f=d-f;
return f;
}
void main()
{
int p,a,b,u,v,r,c,d,M;
printf("请输入一个质数：");
scanf("%d",&p);
printf("\n");
if((P((double)p)==1)&&(p%4==1))
{
b=1;
a=zxj(1,2,p-1,p);
M=(a*a+b*b)/p;
while(M!=1)
{
u=a%M;
if(u>M/2)
u=0-u;
v=b%M;
if(v>M/2)
v=0-v;
r=(u*u+v*v)/M;
c=(a*u+v*b)/M;
d=(a*v-u*b)/M;
a=c;
b=d;
if(a<0)
a=0-a;
if(b<0)
b=0-b;
M=r;
}
printf("%d是一个模四剩一的质数\n",p);
printf("%d,%d,%f",a,b);
}
else
printf("%d不是一个模四剩一的质数",p);
}
修改了一下！
求分啊！追问

89 运行结果一直是1平方加12平方，显然错误了。

追答

#include
#include

int P(double x)
{
int a,b;
b=(int)sqrt(x);
for(a=2;ab)
return 1;
else
return 0;
}

int Q1(int a)
{
int i,j,x=a;
for(i=1;i=1;j--)
{
if(x==i*i+j*j)
{
return i;
break;
}
}

}

int Q2(int b)
{
int i,j,x=b;
for(i=1;i=1;j--)
{
if(x==i*i+j*j)
{
return j;
break;
}
}

}

void main()
{
int p,a,b;
printf("请输入一个质数：");
scanf("%d",&p);
printf("\n");
if((P((double)p)==1)&&(p%4==1))
{
a=Q1(p);
b=Q2(p);
printf("%d是一个模四剩一的质数\n",p);
printf("%d,%d,%f",a,b);
}
else
printf("%d不是一个模四剩一的质数",p);
}
那是你的设计问题了! 程序运行是没问题的！我把这给你了，求给分啊！

追问

我都说要费马降价法的，循环结构嵌套着做我当然会，我是想用数论方法编程。

Answer 4

可不可以给我个费马降价法的链接，我怎么百度不到，你的程序没有注释，我看不懂啊，其实我有个思路，创建一个素数表，双重循环搜索，虽然笨点，但肯定能做出来，费马降价法是什么啊追问

http://wenku.baidu.com/view/c7a6720bf78a6529647d5358.html
这个网站有费马降价法的资料，不过要懂的话不太容易，有些深。

Answer 5

像你这钟问题，一般就是在sqrt ， pow等函数上用得不对，你把它们转换成int 后就损失精度了， 在以后的判断中就很容易因此出现问题。追问

那怎么改？我的2的D次方不用pow,开方不用sqrt ，而结果基本要用整形处理，怎么弄？

Answer 6

b=(int)sqrt(x);
for(a=2;a<=b;a++)
if(x%a==0)
break;
if(a>b)
return 1;
else
return 0;
}
int r(int a,int b,int c)
{
int d,e,f,g;
e=a%c;
g=1;
for(d=0;d<=b;d++)
{
if(b>=(int)pow(2,d))
continue;
else
{
b=b-(int)pow(2,d-1);
for(f=1;f<=d-1;f++)
{
e=((int)pow(e,2))%c;
}
d=0;
}
g=(e*g)%c;
e=a%c;