海风游戏狂欢季-独家活动首发平台

目录

一、关于公约数

二、计算最大公约数的方法

1. 辗转相除法（欧几里得算法）

2. 更相减损法（辗转相减法）

3. 分解质因数法

4. 穷举法

5. 递归法

6. 短除法

三、总结

一、关于公约数

首先 ，先介绍一下公约数：

公约数（公因数），一个能被若干个整数同时整除的的整数，公约数中最大的称为最大公约数。

公约数与公倍数相反，就是既是A的约数同时也是B的约数的数，12和15的公约数有1，3，最大公约数就是3。再举个例子，30和40，它们的公约数有1，2，5，10，最大公约数是10。

计算两个数组的最大公约数，例如计算 a,b两个数的最大公约数。

二、计算最大公约数的方法

1. 辗转相除法（欧几里得算法）

第一步，先是两个数进行 模运算,来求余数 即 a%b

①当a可以被b整除时 （a%b == 0），直接返回 b , b就是最大公约数。例a = 4;b = 2;a%b==0,所以b = 2,就是这两个数的最大公约数。

②当a%b != 0时，则进行辗转交换，这里用第三个变量来接收 c = a%b; 用 a 来接收 b的值,用b来接收c(余数的值)。

例 a = 6,b = 12; c = a%b = 6; a = b = 12; b = c = 6; a%b = 12%6 = 0。 最大公因数为 6。

共有约数中最大的一个

③重复上述①和②

算法流程图

代码展示

//求最大公约数 辗转相除法

#include

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("最大公约数为：%d",ret);

return 0;

}

示例：

2. 更相减损法（辗转相减法）

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

思想

原文是

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

翻译：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；

若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

提取上述的一些思想

例 a = 12, b = 18; b = b - a = 18 - 12 = 6; a >b; a = a - b = 12 - 6 = 6; a = b = 6; 。

算法流程图

代码展示

//更相减损法（辗转相减法）

#include

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("最大公约数是：%d",a);

return 0;

}

示例

3. 分解质因数法

把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数

例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）= 12

代码展示

#include

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)

{

//因为要进行找这个数的共有的因数，所以这里用数组来接收

int arr_a[100] = {0};//放a的所有因数

int arr_b[100] = {0};//放b的所有因数

//进行放因数

fun(arr_a,a);

fun(arr_b,b);

//找出公共的因数，然后相乘

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);//最大公因数

printf("%d和%d的最大公因数是：%d",a,b,ret);

return 0;

}

4. 穷举法

穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。穷举法也称为枚举法

这里的枚举法就是 先 用一个临时变量来接收（a或b） 其中的一个数，然后连个数进行模运算，两个数都模这个临时变量等于零就是最大公约数，否则临时变量每次减一,然后重复上述。

代码展示

//穷举法

#include

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. 递归法

这里的递归法是基于辗转相除法的思想，然后通过递归来实现。

两个数的最大公约数 ，其中 较小的数 和 两个数相除的余数 的最大公约数

当 y / x%y == 0 时 ， y就是最大公约数。

不为0， 就递归 gcd(y,x%y), gcd 下方代码有描述

算法流程图

代码实现

#include

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的最大公因数。以下如有约数出现则为因数

短除法例题：

12的因数有：1、2、3、4、6、12。

18的因数有：1、2、3、6、9、18。

12与18的公因数有：1、2、3、6。

12与18的最大公因数是6。

算法思想：

第一步：先是分别计算处两个数的所有因数，然后分别用数组来进行存放两个数组的所有因数（这里也可以只用一个数组）本例中为方便大家的理解采用两个数组进行存放。

注意：这里的存放也是有技巧的，这里采取的是从大到小进行排序的（当然也可以进行采取从小到大进行排序）

第二步：进行遍历找出相同的因数进行比较，使用一个临时变量用来存放最大公因数

代码展示

#include

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 的最大公因数为 %d",a,b ,ret);

return 0;

}

三、总结

这里比较推荐是用 辗转相除法（欧几里得算法）和 《九章算术》中的 更相减损法

多说一下，因为当时阿明浅浅学过遍辗转相除法，然后不久后就忘干净了，用的时候还要再去反复找，为了方便使用，干脆把 求解最大公约数 的几种常见的方法详细介绍一下，虽然不是最好，但是多少希望对大家有些帮助！

希望大家对这些方法，有更加深刻的印象。

加油！！！