用质因数求最大公因数

对于较大的数字，列出因数会很慢，使用质因数分解会更快。分别分解这两个数字：45 是 $3\cdot 3\cdot 5$，75 是 $3\cdot 5\cdot 5$。它们共有的质数是一个 3 和一个 5。

将共有的质数相乘：$3\cdot 5$ 等于 15，也就是 45 和 75 的最大公因数。一个质数只有在两个数字中都出现时才算共有：45 中有两个 3，但 75 中只有一个，所以只取一个 3。

原理：公因数只能由两个数都含有的质数组成。取每个共有的质数，并尽可能多地取，就能得到最大的公因数。对于指数，取每个共有质数中较小的指数：${3}^{2}\cdot 5$ 和 $3\cdot {5}^{2}$ 得到 $3\cdot 5$。