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

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

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

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