C语言求最大公约数

万卷行思路 05-03 158

前言：

目前咱们对“c中最大公约数怎么求”大体比较重视，同学们都想要知道一些“c中最大公约数怎么求”的相关资讯。那么小编同时在网络上收集了一些对于“c中最大公约数怎么求””的相关内容，希望咱们能喜欢，我们快快来了解一下吧！

给定两个正整数，求它们的最大公约数。

输入：输入多个数据，每行两个正整数且不超过int 范围。

输出：行对应输出最大公约数。

程序：

辗转相除法。

#include <stdio.h>

int gcd(int m, int n); //将辗转相除的过程封装为函数，使主函数结构清晰。

int main(void)

{

int a, b;

while(~scanf("%d%d", &a, &b)){ //多组数据输入时的方式之一与while(scanf("%d%d", &a, &b) !=EOF)用途相同

printf("%d\n", gcd(a, b));

return 0;

}

int gcd(int m, int n)

{

return n ? gcd(n, m % n) : m; //此函数将辗转相除的过程以递归的形式呈现，简化程序属于常规套路。

}

2.更相减损术。

#include<stdio.h>

int main(void)

{

int a,b;

while(scanf("%d %d",&a,&b) == 2){ //利用scanf(）函数的返回值处理输入数据不止一组的情况。

while( a != b ){

if(a > b)

a = a-b;

else

b = b-a;

｝ //将两数中较大的数改为两数之差。

printf("%d\n",a);

}

return 0;

}