C语言编程:输入两个正整数m和n,求它们的最大公约数。
注明解释··谢谢··· 展开
代码及注释如下:
#include <stdio.h>
int GCD(int a,int b)//定义函数,用来计算最大公约数
{
return b==0?a:GCD(b,a%b);
//此处使用了递归,如果b=0,返回a为最大公约数,否则,一直以b与a%b赋给函数,实现辗转相除
}
int main()
{
int a, b ; //定义实参a, b
int answer ; //定义最后结果
scanf ( "%d%d" , &a, &b) ; //取a,b的值
answer = GCD (a, b) ; //把结果赋给answer
printf ( "%d与%d的最大公约数为%d\n" , a , b , answer ) ; //输出结果
}
扩展资料:
辗转相除法求最大公约数的原理:
因为对任意同时整除a和b的数u,有a=su,b=tu,它也能整除r,因为r=a-bq=su-qtu=(s-qt)u。
反过来每一个整除b和r的整数v,有 b=sv , r=tv,它也能整除a,因为a=bq+r=svq+tv=(sq+t)v。
因此a和b的每一个公因子同时也是b和r的一个公因子,反之亦然。
这样由于a和b的全体公因子集合与b和r的全体公因子集合相同,所以a和b的最大公因子必须等于b和r的最大公因子,这就证明了上边的等式。即(a,b)=(b,r)。
因而,可以由此,得到两个数的最大公约数。
{
int a,b,num1,num2,temp;
printf("请输入两个正整数:\n");
scanf("%d,%d",&num1,&num2);
if(num1<num2)/*选出较大数*/
{
temp=num1;
num1=num2;
num2=temp;
}
a=num1,b=num2;
while(b!=0)/*辗转取余算法*/
{
temp=a%b;
a=b;
b=temp;
}
printf("它们的最大公约数为:%d\n",a);
printf("它们的最小公倍数为:%d\n",num1*num2/a);/*两数相乘除最大公约数就是最小公倍数*/
}
#include "stdio.h"
void main()
{
int num1,num2;
printf("请输入两个正整数:\n");
scanf("%d%d",&num1,&num2);
while(num1 != num2)//当两数不等时,不停的用大数减小数,并把结果赋值给大数,相当于求余数
if(num1>num2)
num1 = num1-num2;
else
num2=num2-num1;
printf("他们的最大公约数是%d",num1);
}
inline int gcd(int m,int n)
{
while(m!=n)
{
if(m>n) m-=n;
if(m<n) n-=m;
}
return m;
}
下面调用gcd(,)函数就ok了
void main()
{
int a, b, c;
printf("请输入两个整数:");
scanf("%d%d", &a,&b);
c = a%b;
while(c) {
if(c) {
a = b;
b = c;
}
c = a % b;
}
printf("最大公约数:%d", b);
}
// 输入 20 60;输出 20