C语⾔求最⼤公约数代码及解析
问题描述
从键盘输⼊两个整数，求任意两个正整数的最⼤公约数（GCD）。
最⼤公因数，也称最⼤公约数、最⼤公因⼦，指两个或多个整数共有约数中最⼤的⼀个。a，b的最⼤公约数记为
（a，b），同样的，a，b，c的最⼤公约数记为（a，b，c），多个整数的最⼤公约数也有同样的记号。求最⼤公约数有多种⽅法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。
问题分析
如果有⼀个⾃然数a能被⾃然数b整除，则称a为b的倍数，b为a的约数。⼏个⾃然数公有的约数，叫做这⼏个⾃然数的公约数。公约数中最⼤的⼀个公约数，称为这⼏个⾃然数的最⼤公约数。
根据约数的定义可知，某个数的所有约数必不⼤于这个数本⾝，⼏个⾃然数的最⼤公约数必不⼤于其中任何⼀个数。要求任意两个正整数的最⼤公约数即求出⼀个不⼤于其中两者中的任何⼀个，但⼜能同时整除两个整数的最⼤⾃然数。
c语言如何去学
算法设计
思路有两种：第⼀种，采⽤穷举法按从⼩到⼤（初值为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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。