内容简介:从键盘输入两个整数,求任意两个正整数的最大公约数(GCD)。最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
问题描述
从键盘输入两个整数,求任意两个正整数的最大公约数(GCD)。
最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。
问题分析
如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
根据约数的定义可知,某个数的所有约数必不大于这个数本身,几个自然数的最大公约数必不大于其中任何一个数。要求任意两个正整数的最大公约数即求出一个不大于其中两者中的任何一个,但又能同时整除两个整数的最大自然数。
算法设计
思路有两种:第一种,采用穷举法按从小到大(初值为1,最大值为两个整数当中较小的数)的顺序将所有满足条件的公约数列出,输出其中最大的一个;第二种,按照从大(两个整数中较小的数)到小(到最小的整数1)的顺序求出第一个能同时整除两个整数的自然数,即为所求。
下面对第二种思路进行详细说明。
两个数的最大公约数有可能是其中的小数,所以在按从大到小顺序找寻最大公约数时,循环变量i的初值从小数n开始依次递减,去寻找第一个能同时整除两整数的自然数,并将其输出。需要注意的是,虽然判定条件是i>0,但在找到第一个满足条件的i值后,循环没必要继续下去,如,25和15,最大公约数是5,对于后面的4、3、2、1没必要再去执行,但此时判定条件仍然成立,要结束循环只能借助break语句。
程序流程图:
下面是完整的代码:
#include<stdio.h>
int main()
{
int m, n, temp, i;
printf("输入两个正整数,中间空一格:");
scanf("%d%d", &m, &n);
if(m<n) /*比较大小,使得m中存储大数,n中存储小数*/
{ /*交换m和n的值*/
temp=m;
m=n;
n=temp;
}
for(i=n; i>0; i--) /*按照从大到小的顺序寻找满足条件的自然数*/
if(m%i==0 && n%i==0)
{/*输出满足条件的自然数并结束循环*/
printf("%d 和 %d 最大公约数是 : %d\n", m, n, i);
break;
}
return 0;
}
运行结果:
输入两个正整数,中间空一格:100 150
150 和 100 最大公约数是 : 50
Linux公社的RSS地址 : https://www.linuxidc.com/rssFeed.aspx
本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-11/155461.htm
以上所述就是小编给大家介绍的《C语言求最大公约数代码及解析》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Vue.js前端开发
陈陆扬 / 人民邮电出版社 / 2017-2-1 / CNY 45.00
本书分为10章,包括简介、基础特性、指令、过滤器、过渡、组件、状态管理、常用插件、工程实例和Weex打包。本书从简单的单个实例和基础语法,到工程实例,将系统地讲述Vue.js在项目中的适用场景和具体操作。本书的特点在于案例详实,使读者体会到框架的优点和便捷之处,提升开发效率,最后能将Vue.js运用到实际项目中,避免纸上谈兵的尴尬。一起来看看 《Vue.js前端开发》 这本书的介绍吧!