-
最大公因子
鎖定
最大公因子定義
求兩個整數最大公約數主要的方法：
- 窮舉法：分別列出兩整數的所有約數，並找出最大的公約數。
- 素因數分解：分別列出兩數的素因數分解式，並計算共同項的乘積。
- 輾轉相除法：兩數相除，取餘數重複進行相除，直到餘數為{\displaystyle 0}時，前一個除數即為最大公約數。
兩個整數{\displaystyle a,b}的最大公約數和最小公倍數（lcm）的關係為：
[3]
兩個整數的最大公約數可用於計算兩數的最小公倍數，或分數化簡成最簡分數。
兩個整數的最大公約數和最小公倍數中存在分配律：
最大公因子例子
故54的正約數為
。
同樣地，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)
