首页 > 代码库 > C语言 · 求最大公约数

C语言 · 求最大公约数

算法提高 求最大公约数  
时间限制:1.0s   内存限制:512.0MB
    
编写一函数gcd,求两个正整数的最大公约数。
样例输入: 
5 15
样例输出:
5
样例输入: 
7 2
样例输出:
1

作者注释:常用两种方法:递归法,相减法。

递归法代码:
 1 #include<stdio.h> 
 2 //递归求最大公约数 
 3 int gcd(int m,int n)  
 4 {  
 5     return n==0?m:gcd(n,m%n);  
 6 }
 7 int main(){
 8     int m,n;
 9     scanf("%d%d",&m,&n);
10     printf("%d",gcd(m,n));
11 } 

递减法代码:

#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));
} 

 

C语言 · 求最大公约数