Loading AI tools
能夠整除所有指定的整數的最大正整數 来自维基百科,自由的百科全书
最大公因數(英語:highest common factor,hcf)也稱最大公約數(英語:greatest common divisor,gcd)是數學詞彙,指能夠整除多個非零整數的最大正整數。例如8和12的最大公因數為4。
整數序列的最大公因數可以記為或。
最大公因數的值至少為1,例如;最大則為該組整數中絕對值最小的絕對值,例如和。
求兩個整數最大公因數主要的方法:
兩個整數的最大公因數和最小公倍數(lcm)的關係為:
兩個整數的最大公因數可用於計算兩數的最小公倍數,或分數化簡成最簡分數。
兩個整數的最大公因數和最小公倍數中存在分配律:
54和24的最大公因數是多少?
數字54可以表示為幾組不同正整數的乘積:
故54的正因數為。
同樣地,24可以表示為:
故24的正因數為。
這兩組數列中的共同元素即為54和24的公因數:
其中的最大數6即為54和24的最大公因數,記為:
如果兩數的最大公因數為1,那麼這兩個數互質。例如,9和28就是互質數。
假設有一個大小為24乘60的矩形區域,這個區域可以按照不同的大小劃分正方形網格:1乘1、2乘2、3乘3、4乘4、6乘6、12乘12。因此,12是24和60的最大公因數。大小為24乘60的矩形區域,可以按照12乘12的大小劃分正方形網格,一邊有兩格()、另一邊有五格()。
可以通過質因數分解來計算最大公因數。例如計算,可以先進行質因數分解 和 ,因為其中表達式的「重合」,所以。實踐中,這種方法只在數字比較小時才可行,因為對較大數進行質因數分解通常會耗費大量的時間。
再舉一個用文氏圖表示的例子,計算48和180的最大公因數。首先對這兩個數進行質因數分解:
它們之中的共同元素是兩個2和一個3:
相比質因數分解法,輾轉相除法的效率更高。
計算時,先將48除以18得到商2、餘數12,然後再將18除以12得到商1、餘數6,再將12除以6得到商2、餘數0,即得到最大公因數6。我們只關心每次除法的餘數是否為0,為0即表示得到答案。這一算法更正式的描述是這樣的:
其中
如果參數都大於0,那麼該算法可以寫成更簡單的形式:
以下使用輾轉相除法實現。
private int GCD(int a, int b) {
if(0 != b) while(0 != (a %= b) && 0 != (b %= a));
return a + b;
}
運行時計算實現:
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
}
int GCD(int a, int b) {
if (b) while((a %= b) && (b %= a));
return a + b;
}
private int GCD(int a, int b) {
if (b==0) return a;
return GCD(b, a % b);
}
const GCD = (a, b) => b ? GCD(b, a % b) : a;
GCD = lambda a, b: (a if b == 0 else GCD(b, a % b))
# or
def GCD(a, b):
if b == 0:
return a
return GCD(b, a % b)
![]() | 此章節需要擴充。 (2020年8月30日) |
最大公約數又指一社會中不同陣營勉強所達之共同利益。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.