最大公约数的四种求法(枚举法,短除法,质因数分解法,欧几里德算法)

您所在的位置：网站首页 › 76和500的最大公因数是四吗对吗对吗 › 最大公约数的四种求法(枚举法,短除法,质因数分解法,欧几里德算法)

最大公约数的四种求法(枚举法,短除法,质因数分解法,欧几里德算法)

2024-07-10 10:48| 来源: 网络整理| 查看: 265

最大公约数枚举法:

将两个数的因数分别一一列出，从中找出其公因数，再从公因数中找出最大的一个，即为这两个数的最大公因数。

例：求30与24的最大公因数。

30的正因数有：1,2,3,5,6,10,15,30。

24的正因数有：1,2,3,4,6,8,12,24。

易得其公因数中最大的一个是6，所以30和24的[最大公因数]是6。

短除法：

短除符号就像一个倒过来的除号，[短除法]就是先写出要求最大公因数的两个数A、B，再画一个短除号，接着在原本写除数的位置写两个数公有的[质因数]Z（通常从最小的质数开始），然后在短除号的下方写出这两个数被Z整除的商a，b，对a，b重复以上步骤，以此类推，直到最后的商互质为止，再把所有的除数相乘，其积即为A，B的最大公因数。（[短除法]同样适用于求[最小公倍数]，只需将其所有[除数]与最后所得的商相乘即可）

在这里插入图片描述

最大公约数：2*3=6 .验证：12%6=0，18%6=0

那么最小公倍数：2 3 * 2 *3=36.

质因数分解法

如果一个质数是某个合数的约数，那么就说这个质数是这个合数的质因数，把一个合数用质因数相乘的形式表示，叫做分解质因数。

将需要求最大公因数的两个数A，B分别分解质因数，再从中找出A、B公有的质因数，把这些公有的质因数相乘，即得A、B的最大公约数。

例：求48和36的最大公因数。

把48和36分别分解质因数：

48=2×2×2×2×3

36=2×2×3×3

其中48和36公有的质因数有2、2、3，所以48和36的最大公因数是 2×2×3=12。

求6和15的最小公倍数。先分解质因数，得6=2×3，15=3×5，6和15的全部公有的质因数是3，6独有质因数是2，15独有的质因数是5，2×3×5=30，30里面包含6的全部质因数2和3，还包含了15的全部质因数3和5，且30是6和15的公倍数中最小的一个，所以[6，15]=30。

[欧几里德算法]：核心原理：gcd(a,b) = gcd(b,a mod b) 一个基本的性质：d | a，d | b，d | (a+b)，d | (ax + by) （d能整除a，d能整除b，那么d就能整除a+b，也能整除a的若干倍+b的若干倍）

12和30的最大公约数求解过程：

a=30 b=12 a=12 b=6(30%12) a=6 b=0 (6%6) 结果是6

在这里插入图片描述

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } #include #include using namespace std; int gcd(int a,int b){ return b?gcd(b,a%b): a; } int main() { int n; cin >> n; while (n -- ) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", gcd(a, b)); } return 0; } 最小公倍数

最小公倍数的求法也很简单，最小公倍数= a×b /最大公约数.

这里举一个例子比较好理解： 12 和 30 的最大公约数是 6，那么最小公倍数就是 12×30/6=60.

【本文地址】

最大公约数的四种求法(枚举法,短除法,质因数分解法,欧几里德算法)

最大公约数的四种求法(枚举法,短除法,质因数分解法,欧几里德算法)

今日新闻

推荐新闻