C++ 最大公约数函数__gcd()的用法及其朴素实现 - 张再筵的博客

C++的标准库中提供了一些实用的函数，比如：

__gcd(x,y)函数 用于求x，y的最大公约数

其中x，y不能是浮点数

头文件：#include<algorithm>;

用法：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<__gcd(a,b)<<endl;
}

朴素实现方法：

算法的本质是辗转相除：

1.普通循环

int gcd(int x,int y)
{
    int r;
    while (a%b!=0)
    {
        r=a%b;
        a=b;
        b=r;    
    }
    return b; 
}

2.递归+三元运算符

int gcd(int a,int b) {
    return b>0 ? gcd(b,a%b):a;
}

3.递归+ if 语句

求x 和 y 的最大公约数，就是求 y 和 x % y 的最大公约数

int gcd(int a,int b)
{
    if(a%b==0) 
        return b;
    else 
        return (gcd(b,a%b));
}