^Gustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", [[Wolfram Demonstrations Project]], Published: February 1, 2013.. [2018-06-11]. (原始内容于2020-09-22).
最大公因數, 英語, highest, common, factor, 也稱最大公約數, 英語, greatest, common, divisor, 是數學詞彙, 指能够整除多個整數的最大正整数, 而多個整数不能都为零, 例如8和12的最大公因数为4, 整数序列a, displaystyle, 的最大公因数可以記為, displaystyle, dots, 或gcd, displaystyle, dots, 求兩個整數主要的方法, 列舉法, 分別列出兩整數的所有因數, 並找出最大的公因數, 質因數分解, 分別列出. 最大公因數 英語 highest common factor hcf 也稱最大公約數 英語 greatest common divisor gcd 是數學詞彙 指能够整除多個整數的最大正整数 而多個整数不能都为零 例如8和12的最大公因数为4 整数序列a displaystyle a 的最大公因数可以記為 a 1 a 2 a n displaystyle a 1 a 2 dots a n 或gcd a 1 a 2 a n displaystyle gcd a 1 a 2 dots a n 求兩個整數最大公因數主要的方法 列舉法 分別列出兩整數的所有因數 並找出最大的公因數 質因數分解 分別列出兩數的質因數分解式 並計算共同項的乘積 短除法 兩數除以其共同質因數 直到兩數互質時 所有除數的乘積即為最大公因數 兩個整數a b displaystyle a b 的最大公因數和最小公倍數 lcm 的關係為 gcd a b lcm a b a b displaystyle gcd a b operatorname lcm a b ab 兩個整數的最大公因數可用於計算兩數的最小公倍數 或分數化簡成最簡分數 兩個整數的最大公因數和最小公倍數中存在分配律 gcd a lcm b c lcm gcd a b gcd a c displaystyle gcd a operatorname lcm b c operatorname lcm gcd a b gcd a c lcm a gcd b c gcd lcm a b lcm a c displaystyle operatorname lcm a gcd b c gcd operatorname lcm a b operatorname lcm a c 在直角坐標中 兩頂點為 0 0 a b displaystyle 0 0 a b 的線段會通過gcd a b 1 displaystyle gcd a b 1 個格子點 目录 1 概述 1 1 例子 1 2 互质数 1 3 几何角度的说明 2 计算 2 1 质因数分解法 2 2 辗转相除法 3 性质 4 程式代碼 4 1 C 4 2 C 4 3 C 4 4 Java 4 5 JavaScript 4 6 Python 5 政治用法 6 参考文献 7 外部链接 8 参见概述 编辑例子 编辑 54和24的最大公因数是多少 数字54可以表示為几组不同正整數的乘積 54 1 54 2 27 3 18 6 9 displaystyle 54 1 times 54 2 times 27 3 times 18 6 times 9 故54的正因數為1 2 3 6 9 18 27 54 displaystyle 1 2 3 6 9 18 27 54 同樣地 24可以表示為 24 1 24 2 12 3 8 4 6 displaystyle 24 1 times 24 2 times 12 3 times 8 4 times 6 故24的正因數為1 2 3 4 6 8 12 24 displaystyle 1 2 3 4 6 8 12 24 这两组数列中的共同元素即为54和24的公因数 1 2 3 6 displaystyle 1 2 3 6 其中的最大數6即為54和24的最大公因數 記為 gcd 54 24 6 displaystyle gcd 54 24 6 互质数 编辑 如果两数的最大公因数为1 那么这两个数互質 例如 9和28就是互质数 几何角度的说明 编辑 24乘60的矩形被十个12乘12的正方形格子完全覆盖 即12为24和60的最大公因数 推而广之 如果c是a和b的最大公因数 那么a乘b的矩形就可以被若干个边长为c的正方形格子完全覆盖 假设有一个大小为24乘60的矩形区域 这个区域可以按照不同的大小划分正方形网格 1乘1 2乘2 3乘3 4乘4 6乘6 12乘12 因此 12是24和60的最大公因数 大小为24乘60的矩形区域 可以按照12乘12的大小划分正方形网格 一边有两格 24 12 2 displaystyle frac 24 12 2 另一边有五格 60 12 5 displaystyle frac 60 12 5 计算 编辑质因数分解法 编辑 可以通过質因數分解来计算最大公因数 例如计算gcd 18 84 displaystyle gcd 18 84 可以先进行质因数分解 18 2 3 2 displaystyle 18 2 times 3 2 和 84 2 2 3 7 displaystyle 84 2 2 times 3 times 7 因为其中表达式2 3 displaystyle 2 times 3 的 重合 所以gcd 18 84 6 displaystyle gcd 18 84 6 实践中 这种方法只在数字比较小时才可行 因为对较大数进行质因数分解通常会耗费大量的时间 再举一个用文氏图表示的例子 计算48和180的最大公因数 首先对这两个数进行质因数分解 48 2 2 2 2 3 displaystyle 48 2 times 2 times 2 times 2 times 3 180 2 2 3 3 5 displaystyle 180 2 times 2 times 3 times 3 times 5 它们之中的共同元素是两个2和一个3 1 最小公倍数 2 2 2 2 3 3 5 720 displaystyle 2 times 2 times 2 times 2 times 3 times 3 times 5 720 最大公因数 2 2 3 12 displaystyle 2 times 2 times 3 12 辗转相除法 编辑 相比质因数分解法 辗转相除法的效率更高 计算gcd 18 48 displaystyle gcd 18 48 时 先将48除以18得到商2 余数12 然后再将18除以12得到商1 余数6 再将12除以6得到商2 余数0 即得到最大公因数6 我们只关心每次除法的余数是否为0 为0即表示得到答案 这一算法更正式的描述是这样的 gcd a 0 a displaystyle gcd a 0 a gcd a b gcd b a m o d b displaystyle gcd a b gcd b a mathrm mod b 其中 a m o d b a b a b displaystyle a mathrm mod b a b left lfloor a over b right rfloor 如果参数都大于0 那么该算法可以写成更简单的形式 gcd a a a displaystyle gcd a a a gcd a b gcd a b b displaystyle gcd a b gcd a b b quad 如果 a gt b gcd a b gcd a b a displaystyle gcd a b gcd a b a quad 如果 b gt a source source source source source source source source source source source source source source 使用辗转相除法计算62和36的最大公因数2的演示动画 性质 编辑任意a和b的公因数都是gcd a b displaystyle gcd a b 的因數 gcd displaystyle gcd 函数满足交换律 gcd a b gcd b a displaystyle gcd a b gcd b a gcd displaystyle gcd 函数满足结合律 gcd a gcd b c gcd gcd a b c displaystyle gcd a gcd b c gcd gcd a b c 程式代碼 编辑以下使用輾轉相除法實現 C 编辑 private int GCD int a int b if 0 b while 0 a b amp amp 0 b a return a b C 编辑 运行时计算实现 template lt typename T gt T GCD T a T b if b while a b amp amp b a return a b 编译时计算实现 include lt iostream gt include lt type traits gt template lt typename T std enable if t lt std is integral lt T gt value T gt a std enable if t lt std is integral lt T gt value T gt b gt struct HCF public static const T value HCF lt T a gt b b a a gt b a b b a gt value template lt typename T std enable if t lt std is integral lt T gt value T gt a gt struct HCF lt T a 0 gt public static const T value a int main std wcout lt lt HCF lt int 12 64 gt value lt lt std endl Output 4 C 编辑 int GCD int a int b if b while a b amp amp b a return a b Java 编辑 private int GCD int a int b if b 0 return a return GCD b a b JavaScript 编辑 const GCD a b gt b GCD b a b a Python 编辑 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日 参见 共識決策法和香港核心價值 最大公約數又指一社會中不同陣營勉強所達之共同利益 参考文献 编辑 Gustavo Delfino Understanding the Least Common Multiple and Greatest Common Divisor Wolfram Demonstrations Project Published February 1 2013 2018 06 11 原始内容存档于2020 09 22 外部链接 编辑圖解最大公因數求法 页面存档备份 存于互联网档案馆 包含GCD動態規劃 页面存档备份 存于互联网档案馆 参见 编辑公倍数 公约数 最小公倍数 取自 https zh wikipedia org w index php title 最大公因數 amp oldid 74811539, 维基百科,wiki,书籍,书籍,图书馆,