什么是最大公因子

最佳答案:

最大公因子，又称最大公约数（英语：greatest common divisor，gcd），指两个或多个整数共同具有的最大约数。

详情介绍

最大公因子，又称最大公约数（英语：greatest common divisor，gcd），指两个或多个整数共同具有的最大约数。

中文名

最大公因子

外文名

greatest common divisor

别名

最大公约数

定义

两个或多个整数共同有的最大约数

应用学科

数学

相关术语

最小公倍数

最大公因子定义

最大公因子，又称最大公约数（英语：greatest common divisor，gcd），指两个或多个整数共同具有的最大约数，记为

或

。

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

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

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

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

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

两个整数{displaystyle a,b}的最大公约数和最小公倍数（lcm）的关系为：

两个整数的最大公约数可用于计算两数的最小公倍数，或分数化简成最简分数。

两个整数的最大公约数和最小公倍数中存在分配律：

在直角坐标中，两顶点为

的线段会通过

个格子点。

最大公因子例子

54可以表示为两两不同正整数的乘积：

故54的正约数为

。

同样地，24可以表示为：

故24的正约数为

。

24,54都有的正约数1,2,3,6即为公约数，其中最大的公约数6即为最大公约数，记为

。

最大公因子程式代码

数字之间的最大公约数之所有约数是该组数字所有的公约数。

以下使用辗转相除法实现。

C#

1 private int GCD(int a, int b){

2 if(0 != b) while(0 != (a %= b) && 0 != (b %= a));

3 return a + b;

4 }

C++

运行时计算实现：

template < typename T >

T GCD(T a, T b)

{ if(b) while((a %= b) && (b %= a));

return a + b;}

编译时计算实现：

#include <iostream>

#include <type_traits>

template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a, std::enable_if_t<std::is_integral<T>::value, T> b>

struct HCF{

public:

static const T value=HCF<T, (a>b? b: a), (a>b? a%b: b%a)>::value;

};

template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a>

struct HCF<T, a, 0>{

public:

static const T value=a;

};

int main(){ std::wcout<<HCF<int, 12, 64>::value<<std::endl;//Output: 4}

C

int GCD(int a, int b) {

if(b) while((a %= b) && (b %= a));

return a + b;}

Java

private int GCD(int a, int b){

if(b==0) return a; return a % b == 0 ? b : GCD(b, a % b);}

Python

GCD = lambda a, b: (GCD(b, a % b) if a % b else b)