博客

gcd函数即为实现求两数最大公约数（最大公因数）的函数

求两个整数最大公约数主要的方法：

1.穷举法：分别列出两整数的所有约数，并找出最大的公约数。

2.素因数分解：分别列出两数的素因数分解式，并计算共同项的乘积。

3.短除法：两数除以其共同素因数，直到两数互素时，所有除数的乘积即为最大公约数。

4.辗转相除法：两数相除，取余数重复进行相除，直到余数为0时，前一个除数即为最大公约数。

gcd函数的一些实现方法：

【C++】gcd函数的写法

库函数也有已经实现的gcd函数：


int k=__gcd(n,m);


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

int、long long类型都可以，需要注意的是两个类型必须要相同，还有就是不能用浮点型，它头文件是algorithm。