C语言 · 求最大公约数

时间:2022-08-20 09:29:26
算法提高 求最大公约数  
时间限制:1.0s   内存限制:512.0MB
编写一函数gcd,求两个正整数的最大公约数。
样例输入: 
5 15
样例输出:
5
样例输入: 
7 2
样例输出:
1 作者注释:常用两种方法:递归法,相减法。 递归法代码:
 #include<stdio.h>
//递归求最大公约数
int gcd(int m,int n)
{
return n==?m:gcd(n,m%n);
}
int main(){
int m,n;
scanf("%d%d",&m,&n);
printf("%d",gcd(m,n));
}

递减法代码:

#include<stdio.h>
//相减法求最大公约数
int gcd(int a,int b){
while(a!=b){
if(a>b){
a = a-b;
} else {
b = b-a;
}
}
return a;//最大公约数是a or b
}
int main(){
int m,n;
scanf("%d%d",&m,&n);
printf("%d",gcd(m,n));
}