c语言求最大公约数

#include <stdio.h>
int main(int argc,char *argv[]){
    int a,b,r;
    printf("Input a & b(int a,b>0)...\n");
    if(scanf("%d%d",&a,&b)!=2 || a<1 || b<1){
        printf("Input reeor, exit...\n");
        return 0;
    }
    while(b)
        r=a%b,a=b,b=r;
    printf("The GCD is %d\n",a);
    return 0;
}

求最大公约数的方法有很多。最常用的有如下两种：

1 根据数学定义，可同时整除两个操作数的最大整数，就是最大公约数：

int gcd(int m, int n)//求n和m的最大公约数
{
    int min = m>n?n:m; //两个数的较小者。
    while(min > 0)
    {
        if(m%min == 0 && n%min == 0) break;//都能整除，则为最大公约数。
        min--;
    }
    return min; 
}

2 在算法上，有专门的快速求最大公约数的算法，称为辗转相除法：

以下是该算法的递归实现：

int gcd(int x , int y)
{
    if(!y)return x;
    return gcd(y , x%y);
}

int cacu(int a,int b){
	int temp;
	while(a!=0){
temp=b%a;
		b=a;
a=temp;
	}
	return b;
}
构造函数返回最大公约数
我们用b作为这一次的被除数，a作为这一次的除数，则此次的余数为b%a，temp储存。接下来要为下一次运算做准备，在下一次运算中这次的除数要作为被除数出现，这次的余数要作为除数出现，故将对应的值分别放到对应的位置上（这次出书a的值赋给下一次的被除数b，这次余数temp的值赋给下次的除数a）。关于结束条件，由于余数为0时的除数是我们要求的值，但是在判定时这个值已经被我们当成下一次还未进行的运算的被除数赋给了b，而那个值为0的余数也被我们赋给了下一次的除数a，故可将下一次运算的除数为0作为结束条件，将下一次运算的被除数作为结果返回

纯手打，希望有帮助，给个采纳吧亲~

追问

你的回答很好，循环原理懂了，不懂的是，你这个是不是不完整啊？那个cacu什么意思？最让我困惑的就是在求余时怎么确定大除于小的？和上面有关？输出在哪？return b;?

追答

我的答案只是个计算函数，不是主函数，返回的是最大公约数

因为上面只是要算法，没有要程序，所以就没写主函数。想验证的话用下面这个吧：
int main(){
	int a,b;
	scanf("%d %d",&a,&b);
	while(a!=0&&b!=0){
		printf("%d\n",cacu(a,b));
		scanf("%d %d",&a,&b);
	}
	return 0;
}
PS：cacu是caculate简短写法（个人习惯）

事实上不用确定谁大谁小

如果b>a，即和传统辗转相除无区别；如果a>b，则在执行下次循环时a、b会交换其值（即b%a的值为b，赋给下一次的a，而a的值赋给下一次的b）

另外，楼楼是不是没学写函数啊，其实也可以写成：

#include<stdio.h>
int main(){
    int a,b,temp;
    scanf("%d %d",&a,&b);
    while(a!=0){
        temp=b%a;
        b=a;
        a=temp;
    }
    printf("%d\n",b);
    return 0;
}

 return b;是在写分函数的时候确定返回值用的（估计楼楼过一段时间会了解到吧）

追问

cacu接上面的循环算法？

追答

c语言里可以自己写函数（比如上面的cacu函数），格式是
<返回值类型> <函数名>(<参数列表>){函数体}
已经定义的函数在其他函数中可以被调用，调用时需出现的结构为
<函数名>(<传入参数列表>);
再举个例子，scanf();和printf();就是两种相对特别一点的函数，main()函数也是一种函数，只是更为特殊

更多追问

#include "stdio.h"
int main()
{
int d1,d2,r;
printf("输入两个正整数：");
scanf("%d %d",&d1,&d2);
do
{
r=d1%d2;
d1=d2;d2=r;
}while(d2!=0);
printf("最大公约数是：%d",d1);
}

//递归法
#include "stdio.h"
int fun(int d1,int d2)
{
if(d2!=0)
return fun(d2,d1%d2);
else
return d1;
}
int main()
{
int d1,d2;
printf("输入两个正整数：");
scanf("%d %d",&d1,&d2);
printf("最大公约数是：%d",fun(d1,d2));
}

#include <stdio.h>
void main()
{
	int m,n,k,min,max,i;
	scanf("%d%d",&m,&n);
	if(n<m)
	{
		k=n;
		n=m;
		m=k;
	}
	for(i=m;i>0;i++)
	{
		if((m%i==0)&(n%i==0))
		{
			max=i;
			break;
		}
	}
	min=m*n/max;
	printf("%d和%d的最大公约数是%d\n",m,n,max);
	printf("%d和%d的最小公倍数是%d\n",m,n,min);
}
这个是我的程序，其中利用了最小公倍数是两个数的乘积除以最大公倍数，希望能够帮到你。

追问

我还没学void 和for 可以用int型和while语句解决吗？

追答

#include <stdio.h>
int main()
{
	int m,n,k,min,max,i;
	scanf("%d%d",&m,&n);
	if(n<m)
	{
		k=n;
		n=m;
		m=k;
	}
	i=m;
	while(i>0)
	{
		if((m%i==0)&(n%i==0))
		{
			max=i;
			break;
		}
		i--;
	}
	min=m*n/max;
	printf("%d和%d的最大公约数是%d\n",m,n,max);
	printf("%d和%d的最小公倍数是%d\n",m,n,min);
}
定义main函数的类型的时候，void和int是没有区别的，其实绝大多数时候定的是void，也就是空类型。for语句和while语句是一样的，这个是我修改后的程序，希望同样能帮到你。

追问

我看懂您求最大公约数的方法了，的确很新颖。如果要用辗转相除法应该怎么表示?

追答

#include<stdio.h>

int main()

{

int m,n,r,p,k;

scanf("%d%d",&m,&n);

if(n>m)

{

k=n;

n=m;

m=k;

}

p=m*n;

while(m!=0)

{

r=n%m;

n=m;

m=r;

}

printf("这是最大公约数：%d\n",n);

printf("这是最小公倍数：%d\n",p/n);

return 0;

}

这个是我给你修改后的程序，你的程序思路上是正确的，只是有两个细节错了。

1. 两个数值比较的时候，if里面的语句应该是（n>m),，而不是(n<m);2

2. while里面应该是(m!=0),而不是（m=0);
   

更多追问

#include<stdio.h> 
int gongyue(int m,int n)
{
 int r;
 if(m==n) return m;
 else
  while((r=m%n)!=0)
  {
     m=n;
     n=r;
   }
    return n;
 }
void main()
{
 int a,b,i;
 printf("please input two number:\n");
 scanf("%d%d",&a,&b);
 i=gongyue(a,b);
 printf("最大公约数是:%d\n",gongyue(a,b));
  }

#include "stdio.h"
void main()
{int a,m,n,i;
scanf("%d,%d",&m,&n);//
if(n>m)
{a=m;
m=n;
n=a;
}

for(i=n;i>=1;i--)
{ if(m%i==0&&n%i==0)
break;

}
printf("%d",i);
}

int divisor (int a,int b)    /*自定义函数求两数的最大公约数*/
{
  int  temp;          /*定义整型变量*/
  if(a<b)             /*通过比较求出两个数中的最大值和最小值*/
  { 
      temp=a;
      a=b;
      b=temp;
    } /*设置中间变量进行两数交换*/
   while(b!=0)           /*通过循环求两数的余数，直到余数为0*/
   {
      temp=a%b;
      a=b;              /*变量数值交换*/
      b=temp;
    }
  return a;            /*返回最大公约数到调用函数处*/ 
}

#include"stdio.h"
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
int main()
{
    int i,j,k,mmax,mmin;
	scanf("%d%d",&i,&j);
	if(i==j){
	   printf("%d\n",i);
	}
	else{
        mmax = max(i,j);
        mmin = min(i,j);
        while(mmax!=mmin){
             k=mmax-mmin;
             if(k>mmin){
                 mmax = k;
             }
             if(k<=mmin){
                 mmax=mmin;
                 mmin=k;
            }
            //printf("%d %d\n",mmax,mmin);
        }
        printf("%d\n",mmax);
	}
	return 0;
}

//求两个数的最大公约数和最小公倍数
void fun(int a,int b)
{
    int temp,r;
    int v;
     
    if(a<b)
    {temp=a; a=b; b=temp;}    //将大数放在a中,小数放在b
    v=a*b;
    r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    v/=b;
    printf("最大公约数为%d\n",b);
    printf("最小公倍数为%d\n",v);
}

这是求最小公倍数和最大公约数的函数，希望对你有所帮助。