公約數,亦稱公因數。是一個能被若干個整數同時均整除的整數。如果一個整數同時是幾個整數的約數,稱這個整數為它們的公約數;公約數中最大的稱為最大公約數。對任意的若干個正整數,1總是它們的公因數。
最大公因數,也稱最大公約數、最大公因子,指兩個或多個整數共有約數中最大的一個。
求最大公約數有多種方法,常見的有:質因數分解法、短除法、輾轉相除法、更相減損法。
與最大公約數相對應的概念是最小公倍數。
公約數,亦稱公因數。是一個能被若干個整數同時均整除的整數。如果一個整數同時是幾個整數的約數,稱這個整數為它們的公約數;公約數中最大的稱為最大公約數。對任意的若干個正整數,1總是它們的公因數。
最大公因數,也稱最大公約數、最大公因子,指兩個或多個整數共有約數中最大的一個。
求最大公約數有多種方法,常見的有:質因數分解法、短除法、輾轉相除法、更相減損法。
與最大公約數相對應的概念是最小公倍數。
方法一:
質因數分解法:把幾個數先分別分解質因數,再把各數中的全部公有的質因數和獨有的質因數提取出來連乘,所得的積就是這幾個數的最小公倍數。
方法二:
短除法:先用這幾個數的公約數連續去除,一直除到所有的商互質為止,然後把所有的除數連乘起來,所得的積就是這幾個數的最大公約數。
方法三:
輾轉相除法:先求出其中任意兩個數的最大公約數,再求這個最大公約數與第三個數的最大公約數,依次求下去,直到最後一個數為止。最後所得的那個最大公約數,就是所有這
求最大公約數有多種方法,常見的有質因數分解法、短除法、輾轉相除法、更相減損法。如果有一個自然數a能被自然數b整除,則稱a為b的倍數,b為a的約數。幾個自然數公有的約數,叫做這幾個自然數的公約數。公約數中最大的一個公約數,稱為這幾個自然數的最大公約數。
輾轉相除法使用到的原理很聰明也很簡單,假設用f(x,y)表示x,y的最大公約數,取k=x/y,b=x%y,則x=ky+b,如果一個數能夠同時整除x和y,則必能同時整除b和y;而能夠同時整除b和y的數也必能同時整除x和y,即x和y的公約數與b和y的公約數是相同的,其最大公約數也是相同的,則有f(x,y)=f(y,x%y)(y>0),如此便可把原問題轉化為求兩個更小數的最大公約數,直到其中一個數為0,剩下的另外一個數就是兩者最大的公約數。
例如,12和30的公約數有:1、2、3、6,其中6就是12和30的最大公約數。