2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

ユークリッドの互除法 – Wikipedia

素因数分解しなくても、ユークリッドの互除法という方法を使えば、もっと早く算出できるという事がわかった。

というか、読んだから分かったんだけど。

20と12なら

20/12 = 1あまり8

12 / 8 = 1 あまり 4

8 / 4 = 2 あまり 0

で4が最大公約数となる。

これは、便利な方法だ。