No1.　最大公約数を見つけよう

問題

解説

※この解説では、ＡとＢを、ある２つの数とします。

最大公約数とは
Ａの約数でもあり、Ｂの約数でもある約数を、ＡとＢの公約数といいます。

公約数のうち、一番大きな公約数を最大公約数といいます。

最大公約数の見つけ方
最大公約数は、素因数分解をすれば、すぐに見つけることができます。

２つの数ＡとＢをそれぞれ素因数分解したとき、次のようになったとします。（●や▲などを素因数といいます。ＡやＢの部品のようなものです。）
Ａ＝●●▲■
Ｂ＝●▲▲

このとき、ＡとＢの最大公約数は、
●▲
になります。
最大公約数は、Ａの中にもあり、Ｂの中にもある、共通の部品です。

共通の部品が１つもないとき、最大公約数は 1 になります。

また、ＡとＢの最大公約数の約数が、ＡとＢの公約数になります。