首页 > 代码库 > c语言求两个数的最大公因数（穷举法，欧几里得算法，递归）
c语言求两个数的最大公因数（穷举法，欧几里得算法，递归）
/*主函数Gcd为求公因数的函数输入为负时返回-1*/
int main()
{
int a, b;
printf("Input a,b:");
scanf("%d,%d",&a,&b);
if (a < 0 || b < 0)
printf("Input number should be positive!\n");
else
printf("Greatest Common Divisor of %d and %d is %d\n",a,b,Gcd(a,b));
return 0;
}
/*穷举法一（欧几里得）*/
int Gcd(int a,int b)
{
int i,t;
if(a<=0 || b<=0)
return -1;
t=a<b ? a : b;
for(i=t;i>0;i--)
{
if(a%i==0 && b%i==0)return i;
}
return 1;
}
/*穷举法二*/
int Gcd(int a,int b)
{
int r;
if(a<=0 || b<=0)
return -1;
do
{
r=a%b;
a=b;
b=r;
}while(r!=0);
return a;
}
/*递归一*/
int Gcd(int a,int b)
{
if(a<=0 || b<=0)
return -1;
if(a%b==0)
return b;
else
return Gcd(b,a%b);
}
/*递归二*/int Gcd(int a, int b)
{
if (a <= 0 || b <= 0)
return -1;
while (a != b)
{
if (a > b)
a = a - b;
else if (b > a)
b = b - a;
}
return a;
}
/*递归二是根据公因数的如下性质：
根据最大公约数的如下3条性质，采用递归法编写计算最大公约数的函数Gcd()，
在主函数中调用该函数计算并输出从键盘任意输入的两正整数的最大公约数。
性质1 如果a>b，则a和b与a-b和b的最大公约数相同，即Gcd(a, b) = Gcd(a-b, b)
性质2 如果b>a，则a和b与a和b-a的最大公约数相同，即Gcd(a, b) = Gcd(a, b-a)
性质3 如果a=b，则a和b的最大公约数与a值和b值相同，即Gcd(a, b) = a = b
*/
c语言求两个数的最大公因数（穷举法，欧几里得算法，递归）