#include
#include
#include
#include
int zdgys(int x,int y)//求最大公约数
{
int m,r;
if(x>y)
{
r=x%y;
while(r)
{
x=y;
y=r;
r=x%y;
}
m=y;
}
else {
r=y%x;
while(r)
{
y=x;
x=r;
r=y%x;
}
m=x;
}
return m;
}
int is_prime(int n)//判断质数
{
int i;
if(n<=1) return 0;
int m = floor(sqrt(n)+0.5);
for(i=2;i<=m;i++)
if(n%i==0) return 0;
return 1;
}
int is_pfs(int m)//判断平方数
{
if(sqrt(m)==(int)(sqrt(m))) return 1;
return 0;
}
int min(x,y)//求最小数
{
if(x>y) return y;
else return x;
}
int main()
{
int x,y;
while(scanf("%d %d",&x,&y)!=EOF)
if(x<100&&y<100)
{
printf("%d\n",min(x,y));
}
else{
int q=zdgys(x,y);
while(zdgys(x,y)>=100&&!is_prime(zdgys(x,y)))
{
int t=zdgys(x,y);
int i,q;
for(i=2;i<=t;i++)
{
if(t%i==0&&i<100&&t/i<100)
{
q=t/i;
break;
}
}
}
if(is_pfs(q)||is_prime(q))
{
printf("%d\n",min(x,y));
}
}
}
我觉得我算法没什么问题吧,但是提交一直TLE。请问各位大佬如何优化这个算法。另外请问是不是调用函数越多,时间花费越大