词条信息

admin
admin
超级管理员
词条创建者 发短消息   

相关词条

热门词条

更多>>
什么是端口?到底是做什么的呢?
端口一般指两种,一种是硬件比如路由器或者交换机的插网线的端口,一种是软件的逻辑的概念,比如http的80端口!...
7种进阶方法让你快速测试端口连通性
Ping是Windows、Linux和Unix系统下的一个检查网络连通性的命令工具,对于大部分互联网用户来说很...
电脑开机,总需要按F1,是什么原因造成的?
一.主板掉电这个说法是行业内的叫法了,一般是主板的CMOS电池没电了导致的。也是最常见的一种提示你按F1的提示...
社保降费对个人有什么影响?
下调城镇职工基本养老保险单位缴费比例是政府给企业发的一个大红包,特别是对于企业来说是一个利好,但是对个人来说有...
车辆“出险”对下年保费的影响,到底有多大?
【出险对交强险的影响】【出险对商业险的影响】车辆“出险”对下年保费的影响,到底有多大?这里有必要先提下车险第三...

精选图集

更多>>
简易百科旧版 >>所属分类 >> C/C#   

C语言求最大公约数代码

标签: C语言 最大公约数 代码

顶[0] 发表评论(0) 编辑词条

问题描述


从键盘输入两个整数,求任意两个正整数的最大公约数(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 最大公约数是 : %dn", m, n, i);

break;

}

return 0;

}


运行结果:


输入两个正整数,中间空一格:100 150


150 和 100 最大公约数是 : 50

 

 

附件列表


按字母顺序浏览:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

→我们致力于为广大网民解决所遇到的各种电脑技术问题
 如果您认为本词条还有待完善,请 编辑词条

上一篇C语言列出真分数序列代码及解析
下一篇北京商报:微信支付与民生银行在争什么

0
1. 本站部分内容来自互联网,如有任何版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
2. 本站内容仅供参考,如果您需要解决具体问题,建议您咨询相关领域专业人士。
3. 如果您没有找到需要的百科词条,您可以到百科问答提问或创建词条,等待高手解答。

关于本词条的提问

查看全部/我要提问>>