目錄
一、關(guān)于公約數(shù)
二、計(jì)算最大公約數(shù)的方法?
1. 輾轉(zhuǎn)相除法（歐幾里得算法）
2. 更相減損法（輾轉(zhuǎn)相減法）
3. 分解質(zhì)因數(shù)法
4. 窮舉法?
5. 遞歸法
6. 短除法
三、總結(jié)
一、關(guān)于公約數(shù)
首先 ，先介紹一下公約數(shù)：
公約數(shù)（公因數(shù)），一個(gè)能被若干個(gè)整數(shù)同時(shí)整除的的整數(shù)，公約數(shù)中最大的稱為最大公約數(shù)。
公約數(shù)與公倍數(shù)相反，就是既是A的約數(shù)同時(shí)也是B的約數(shù)的數(shù)，12和15的公約數(shù)有1，3，最大公約數(shù)就是3。再舉個(gè)例子，30和40，它們的公約數(shù)有1，2，5，10，最大公約數(shù)是10。
計(jì)算兩個(gè)數(shù)組的最大公約數(shù)，例如計(jì)算 a,b兩個(gè)數(shù)的最大公約數(shù)。
二、計(jì)算最大公約數(shù)的方法?
1. 輾轉(zhuǎn)相除法（歐幾里得算法）
第一步，先是兩個(gè)數(shù)進(jìn)行 模運(yùn)算,來(lái)求余數(shù)???即 a%b
①當(dāng)a可以被b整除時(shí) （a%b == 0），直接返回 b , b就是最大公約數(shù)。例a = 4;b = 2;a%b==0,所以b = 2,就是這兩個(gè)數(shù)的最大公約數(shù)。
②當(dāng)a%b != 0時(shí)，則進(jìn)行輾轉(zhuǎn)交換，這里用第三個(gè)變量來(lái)接收 c = a%b; 用 a 來(lái)接收 b的值,用b來(lái)接收c(余數(shù)的值)。
例 a = 6,b = 12;?c = a%b = 6;? ? a = b = 12;? b = c = 6;? a%b = 12%6 = 0。 最大公因數(shù)為 6。
共有約數(shù)中最大的一個(gè)
③重復(fù)上述①和②?
算法流程圖
代碼展示?
//求最大公約數(shù) 輾轉(zhuǎn)相除法
#include <stdio.h>
int fun(int a,int b)
{
while (a % b != 0)
{
int c = a % b;
a = b;
b = c;
}
return b;
}
int main()
{
int a = 0;
int b = 0;
scanf("%d %d",&a,&b);
int ret = fun(a,b);
printf("最大公約數(shù)為：%d",ret);
return 0;
}示例：
2. 更相減損法（輾轉(zhuǎn)相減法）
更相減損術(shù)是出自《九章算術(shù)》的一種求最大公約數(shù)的算法，它原本是為約分而設(shè)計(jì)的，但它適用于任何需要求最大公約數(shù)的場(chǎng)合。
思想
原文是
可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。
翻譯：
第一步：任意給定兩個(gè)正整數(shù)；判斷它們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；
若不是則執(zhí)行第二步。
第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止。
則第一步中約掉的若干個(gè)2的積與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。
其中所說(shuō)的“等數(shù)”，就是公約數(shù)。求“等數(shù)”的辦法是“更相減損”法。
提取上述的一些思想
例 a = 12, b = 18;? b = b - a = 18 - 12 = 6; a >b; a = a - b = 12 - 6 = 6; a = b = 6; 。
算法流程圖
代碼展示?
//更相減損法（輾轉(zhuǎn)相減法）
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d",&a,&b);
while (a != b)
{
if (a > b)
a = a - b;
else
b = b - a;
}
printf("最大公約數(shù)是：%d",a);
return 0;
}示例
3. 分解質(zhì)因數(shù)法
?把每個(gè)數(shù)分別分解質(zhì)因數(shù)，再把各數(shù)中的全部公有質(zhì)因數(shù)提取出來(lái)連乘，所得的積就是這幾個(gè)數(shù)的最大公約數(shù)
例如：求24和60的最大公約數(shù)，先分解質(zhì)因數(shù)，得24=2×2×2×3，60=2×2×3×5，24與60的全部公有的質(zhì)因數(shù)是2、2、3，它們的積是2×2×3=12，所以，（24，60）= 12
代碼展示
#include<stdio.h>
void fun(int * arr,int n)
{
int i = 2, j = 0;
while (n > 1)
{
if (n % i == 0)
{
arr[j++] = i;
n /= i;
}
else
{
i++;
}
}
}
int gcd(int a,int b)
{
//因?yàn)橐M(jìn)行找這個(gè)數(shù)的共有的因數(shù)，所以這里用數(shù)組來(lái)接收
int arr_a[100] = {0};//放a的所有因數(shù)
int arr_b[100] = {0};//放b的所有因數(shù)
//進(jìn)行放因數(shù)
fun(arr_a,a);
fun(arr_b,b);
//找出公共的因數(shù)，然后相乘
int i = 0, j = 0, ret = 1;
while (arr_a[i] != 0 && arr_b[j] != 0)
{
if (arr_a[i] == arr_b[j])
{
ret *= arr_a[i];
i++;
j++;
}
else if (arr_a[i] > arr_b[j])
{
j++;
}
else
{
i++;
}
}
return ret;
}
int main()
{
int a = 0;
int b = 0;
scanf("%d %d",&a,&b);
int ret = gcd(a,b);//最大公因數(shù)
printf("%d和%d的最大公因數(shù)是：%d",a,b,ret);
return 0;
}?
4. 窮舉法?
?窮舉法的基本思想是根據(jù)題目的部分條件確定答案的大致范圍，并在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到全部情況驗(yàn)證完畢。若某個(gè)情況驗(yàn)證符合題目的全部條件，則為本問(wèn)題的一個(gè)解；若全部情況驗(yàn)證后都不符合題目的全部條件，則本題無(wú)解。窮舉法也稱為枚舉法
這里的枚舉法就是 先?用一個(gè)臨時(shí)變量來(lái)接收（a或b） 其中的一個(gè)數(shù)，然后連個(gè)數(shù)進(jìn)行模運(yùn)算，兩個(gè)數(shù)都模這個(gè)臨時(shí)變量等于零就是最大公約數(shù)，否則臨時(shí)變量每次減一,然后重復(fù)上述。
代碼展示?
//窮舉法
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d",&a,&b);
int t = a;
while (t--)
{
if (a % t == 0 && b % t == 0)
break;
}
printf("%d",t);
return 0;
}5. 遞歸法
這里的遞歸法是基于輾轉(zhuǎn)相除法的思想，然后通過(guò)遞歸來(lái)實(shí)現(xiàn)。
兩個(gè)數(shù)的最大公約數(shù) ，其中 較小的數(shù)? 和 兩個(gè)數(shù)相除的余數(shù) 的最大公約數(shù)
當(dāng) y / x%y == 0 時(shí) ， y就是最大公約數(shù)。
不為0， 就遞歸 gcd(y,x%y),? gcd 下方代碼有描述
算法流程圖
代碼實(shí)現(xiàn)?
#include<stdio.h>
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b,a%b);
}
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int ret = gcd(a,b);
printf("%d",ret);
return 0;
}6. 短除法
例如：求12與18的最大公因數(shù)。以下如有約數(shù)出現(xiàn)則為因數(shù)
短除法例題：
12的因數(shù)有：1、2、3、4、6、12。
18的因數(shù)有：1、2、3、6、9、18。
12與18的公因數(shù)有：1、2、3、6。
12與18的最大公因數(shù)是6。
算法思想：
第一步：先是分別計(jì)算處兩個(gè)數(shù)的所有因數(shù)，然后分別用數(shù)組來(lái)進(jìn)行存放兩個(gè)數(shù)組的所有因數(shù)（這里也可以只用一個(gè)數(shù)組）本例中為方便大家的理解采用兩個(gè)數(shù)組進(jìn)行存放。
注意：這里的存放也是有技巧的，這里采取的是從大到小進(jìn)行排序的（當(dāng)然也可以進(jìn)行采取從小到大進(jìn)行排序）
第二步：進(jìn)行遍歷找出相同的因數(shù)進(jìn)行比較，使用一個(gè)臨時(shí)變量用來(lái)存放最大公因數(shù)
?代碼展示
#include<stdio.h>
void fac(int* arr, int n)
{
int i = 0;
int j = 0;
int k = 0;
for (i = 1; i <= n; i++)
{
if (n % i == 0)
{
arr[k++] = i;
}
}
}
int gcd(int a, int b)
{
int arr1[100] = { 0 };
int arr2[100] = { 0 };
fac(arr1, a);
fac(arr2, b);
//求同找最大
int i = 0, j = 0, max = 1;
while (arr1[i] != 0 && arr2[j] != 0)
{
if (arr1[i] == arr2[j])
{
if (max < arr1[i])
{
max = arr1[i];
}
i++;
j++;
}
else if (arr1[i] < arr2[j])
{
i++;
}
else
{
j++;
}
}
return max;
}
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int ret = gcd(a, b);
printf("%d 和 %d 的最大公因數(shù)為 %d",a,b ,ret);
return 0;
}
三、總結(jié)
這里比較推薦是用 輾轉(zhuǎn)相除法（歐幾里得算法）和 《九章算術(shù)》中的 更相減損法
多說(shuō)一下，因?yàn)楫?dāng)時(shí)阿明淺淺學(xué)過(guò)遍輾轉(zhuǎn)相除法，然后不久后就忘干凈了，用的時(shí)候還要再去反復(fù)找，為了方便使用，干脆把 求解最大公約數(shù) 的幾種常見(jiàn)的方法詳細(xì)介紹一下，雖然不是最好，但是多少希望對(duì)大家有些幫助！
希望大家對(duì)這些方法，有更加深刻的印象。
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-720321.html
加油?。?！?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-720321.html
到了這里，關(guān)于求最大公約數(shù)的幾種常見(jiàn)的方法 【詳解】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
