素因数から最大公約数を求める

大きな数では因数を列挙するのに時間がかかりますが、素因数分解を使うとより速く求められます。両方の数を因数分解すると、45 は $3\cdot 3\cdot 5$、75 は $3\cdot 5\cdot 5$ です。共通する素数は 3 が 1 つと 5 が 1 つです。

共通する素数を掛けると、$3\cdot 5$ は 15 で、45 と 75 の最大公約数です。素数は、両方の数に現れる回数分だけ共通とみなします。45 には 3 が 2 つありますが、75 には 1 つしかないため、3 は 1 つだけ含めます。

うまくいく理由：共通因数は、両方の数に含まれる素数からしか作れません。共通する素数を、両方が許す限りそれぞれ使うことで、最大の共通因数が作られます。指数がある場合は、共通する素数ごとに小さい方の指数を使います。${3}^{2}\cdot 5$と$3\cdot {5}^{2}$から、$3\cdot 5$が得られます。