Question

用分解质因数求两个数的最大公因数的的方法

求解啊，上午生病了没听这节数学课，一看作业全傻了，跪求用分解质因数求两个数的最大公因数的的方法

Answer 1

求最大公因数常用以下方法：

比如45和96的最大公因数：
先将45分解质因数，得：
45=3×3×5
再将96分解质因数：
96=2×2×2×2×2×3
现在，找出它们的公共因数，找到一个就记下来，再划去，最后得到一个3

因此45和96的最大公因数是3.

类似的，78和12的最大公因数：
78=2×3×13
12=2×2×3
我们找出了一个2和一个3，因此两数的最大公因数是2×3=6，表示为：
（78，12）=6 或 gcd（78,12）=6

特殊情况下的最大公因数：
1.如果两个数中，一个数是另一个的倍数，则较小的数是两数的最大公因数；
2.如果两个数互质，则最大公因数是1；
3.如果两个数相等，那么显然最大公因数是这两个数中的任意一个。

Answer 2

例如：求18和24的最大公因数。先将18和24分解质因数：18=2×3×3 24=2×2×2×3，那么，18的质因数有2，3，3共3个；24的质因数有2，2，2，3共四个 ，他们公有的质因数有一个2和一个3，最大公因数等于公有质因数的积，即2×3=6

Answer 3

扩展欧几里得算法
（辗转相除法）