今天来讲讲最大公因数的几种求法，最近老遇到这个问题

大家好，欢迎来到IT知识分享网。

方法一：辗转相除法

原理很聪明也很简单，假设要求两个数x,y(x<y),的最大公因数，那么先判断y%x==0；如果不等于0，令y=x,x=y%x就用较小的x除以y%x的值，一直到y%x==0,所得x即为所求；

那么c语言如何实现这一过程呢

先看看如何用函数实现

使用递归函数实现辗转相除法求两正整数的最大公约数，调用该函数后，返回两正数的最大公约数。

函数接口定义：

在这里描述函数接口。例如： int gcd(int a,int b);

在这里解释接口参数。例如：其中 a 和 b 都是用户传入的参数，保证传入的参数为正数。 函数须返回 a 和 b 的最大公约数。

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如： #include <stdio.h> int gcd(int a,int b); int main() { int a,b; scanf("%d %d",&a,&b); printf("%d 和 %d 的最大公约数为: %d",a,b,gcd(a,b)); } /* 请在这里填写答案 */

输入样例：

在这里给出一组输入。例如：

18 45 

输出样例：

在这里给出相应的输出。例如：

18 和 45 的最大公约数为: 9

#include<stdio.h> int gcd(int m,int n) { if(n%m==0) return m; else return gcd(n%m,m);/让余数和较小数成为不断使用用的数/ }

 再看看如何不用函数实现这一过程

本题目要求读入2个正整数A和B，然后输出它们的最大公约数和最小公倍数。

输入格式:

输入在一行中给出2个不超过10000的正整数A和B。

输出格式:

对每一组输入，在一行中输出最大公约数和最小公倍数，用逗号分隔。

输入样例:

2 3 

输出样例:

1,6

#include<stdio.h> int main() { int A,B,m,a,b,n; scanf("%d %d",&A,&B); m=A; if(A>B) { A=B; B=m; } /这里交换AB,以保证A小B大/ b=B%A; /余数为b/ a=A; /较小数为a/ while(b>0) { n=b; b=a%n; /较小数除以余数/ a=n; } printf("%d,%d",n,A*B/n); /最大公倍数就是两个数的乘积除以最大公约数/ }

 方法二：质因数分解法

质因数分解法：把每个数分别分解质成因数，然后找出相同的质因数，最后将这些相同的质因数相乘得到最大公约数。例如：

已知两个数分别为24和36，将它们分别进行质因数分解：

24=2×2×2×3

36=2×2×3×3

可以看出，两个数的最大公因数为：

2×2×3=12

因此，24和36的最大公约数为12。

输入一个正整数n，如果n为合数除了1和本身，还有因数的称为合数)，将n进行质因数分解。例如，输入100，输出2、2、5、5，当输入不为合数时，输出error

输入格式:

请在这里写输入格式。例如：输入一个正整数n。

输出格式:

请在这里描述输出格式。例如：当 n 为合数时，输出所有因数 ； 当n 为质数时，输出error。

输入样例:

在这里给出一组输入。例如：

100 

输出样例:

在这里给出相应的输出。例如：

2 2 5 5 

#include<stdio.h> int main() { int n,i,f; scanf("%d",&n); f=n; for(i=2;i<n;i++) { while(f%i==0) { printf("%d ",i); f=f/i; } } if(f==n) printf("error"); }

 这个代码可以找出他的质因数，我们可以稍作加工就可以找出他们共有的质因数，进而求出最大公约数。

方法三：短除法

短除法：在求两个数的最大公约数时，如果无法进行质因数分解，可以采用短除法。短除法的步骤如下：将除数除以被除数得到商，然后用除数除以商得到余数，再用余数去除除数，如此反复，直到余数为零为止。最后将所有的除数相乘，得到的积即为最大公约数。例如：

已知两个数分别为18和24，可以使用短除法求解最大公约数：

18÷2=9

24÷2=12

9÷3=3

12÷3=4

2×3=6

因此，18和24的最大公约数为6。

这个方法与质因数分解法极为相似，而且大家最早接触的就是这种方法，因此较好理解，就不多解释了。

欢迎大家积极留言！