基本概念
如果數(shù)a能被數(shù)b整除，a就叫做b的倍數(shù)瘪板，b就叫做a額約數(shù)。
幾個(gè)整數(shù)中公有的約數(shù)漆诽，叫做這幾個(gè)數(shù)的公約數(shù)侮攀；其中最大的一個(gè)，叫做這幾個(gè)數(shù)的最大公約數(shù)拴泌。
幾個(gè)自然數(shù)公有的倍數(shù)魏身，叫做這幾個(gè)數(shù)的公倍數(shù)，其中最小的一個(gè)自然數(shù)蚪腐，叫做這幾個(gè)數(shù)的最小公倍數(shù)
求法
質(zhì)因數(shù)分解法
質(zhì)因數(shù)分解法：把每個(gè)數(shù)分別分解質(zhì)因數(shù)箭昵，再把各數(shù)中的全部公有質(zhì)因數(shù)提取出來連乘，所得的積就是這幾個(gè)數(shù)的最大公約數(shù)回季。
短除法
短除法:短除法求最大公約數(shù)家制，先用這幾個(gè)數(shù)的公約數(shù)連續(xù)去除，一直除到所有的商互質(zhì)為止泡一，然后把所有的除數(shù)連乘起來颤殴，所得的積就是這幾個(gè)數(shù)的最大公約數(shù)。
輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法是求兩個(gè)自然數(shù)的最大公約數(shù)的一種方法鼻忠，也叫做歐幾里得算法涵但。
例如，求（319帖蔓，377）：
∵ 319÷377=0（余319）
∴（319矮瘟，377）=（377，319）塑娇；
∵ 377÷319=1（余58）
∴（377澈侠，319）=（319，58）埋酬；
∵ 319÷58=5（余29）
∴ （319哨啃，58）=（58，29）写妥；
∵ 58÷29=2（余0）
∴ （58拳球，29）= 29；
∴ （319珍特，377）=29醇坝。
可以寫成右邊的格式。
用輾轉(zhuǎn)相除法求幾個(gè)數(shù)的最大公約數(shù)次坡，可以先求處其中任意兩個(gè)數(shù)的最大公約數(shù)呼猪，再求這個(gè)最大公約數(shù)與第三個(gè)數(shù)的最大公約數(shù)，依次求下去砸琅，直到最后一個(gè)樹為止宋距。最后所得的那個(gè)最大公約數(shù)，就是所有這些數(shù)的最大公約數(shù)症脂。
下面是輾轉(zhuǎn)相除法的算法實(shí)現(xiàn)
// 最大公約數(shù)
public static int gcd(int p, int q) {
if(q == 0) return p;
int r = p % q;
return gcd(q ,r);
}
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int x = gcd(m, n);
int lcm = m*n/x;
System.out.println("最大公約數(shù)為：" + x);
System.out.println("最最小公倍數(shù)為：" + lcm);
更相減損法
更相減損法：也叫更相減損術(shù)谚赎，是出自《九章算術(shù)》的一種求最大公約數(shù)的算法，它原本是為約分)而設(shè)計(jì)的诱篷，但它適用于任何需要求最大公約數(shù)的場(chǎng)合壶唤。
《九章算術(shù)》是中國(guó)古代的數(shù)學(xué)專著，其中的“更相減損術(shù)”可以用來求兩個(gè)數(shù)的最大公約數(shù)棕所，即“可半者半之闸盔，不可半者，副置分母琳省、子之?dāng)?shù)迎吵，以少減多，更相減損针贬，求其等也击费。以等數(shù)約之¤胨”
翻譯成現(xiàn)代語言如下：
第一步：任意給定兩個(gè)正整數(shù)蔫巩；判斷它們是否都是偶數(shù)。若是快压，則用2約簡(jiǎn)圆仔；若不是則執(zhí)行第二步。
第二步：以較大的數(shù)減較小的數(shù)嗓节，接著把所得的差與較小的數(shù)比較荧缘，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作拦宣，直到所得的減數(shù)和差相等為止截粗。
則第一步中約掉的若干個(gè)2與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。
其中所說的“等數(shù)”鸵隧，就是最大公約數(shù)绸罗。求“等數(shù)”的辦法是“更相減損”法。所以更相減損法也叫等值算法豆瘫。
例1．用更相減損術(shù)求98與63的最大公約數(shù)珊蟀。
解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以育灸，98和63的最大公約數(shù)等于7腻窒。
這個(gè)過程可以簡(jiǎn)單的寫為：
（98，63）=（35磅崭，63）=（35儿子，28）=（7，28）=（7砸喻，21）=（7柔逼，14）=（7，7）=7.
例2．用更相減損術(shù)求260和104的最大公約數(shù)割岛。
解：由于260和104均為偶數(shù)愉适，首先用2約簡(jiǎn)得到130和52，再用2約簡(jiǎn)得到65和26癣漆。
此時(shí)65是奇數(shù)而26不是奇數(shù)维咸，故把65和26輾轉(zhuǎn)相減：
65-26=39
39-26=13
26-13=13
所以，260與104的最大公約數(shù)等于13乘以第一步中約掉的兩個(gè)2扑媚，即1322=52腰湾。
這個(gè)過程可以簡(jiǎn)單地寫為：
（260,104）(/2/2) =>（65,26）=（39,26）=（13,26）=（13,13）=13. (22) => 52 [1]
