はじめに

数学ガールの秘密ノートを読んでいて、わかってたつもりがわかってなかったり、「具体的にどういうことなの？」ってのがあいまいなままの理解だったり。そこで流すのももったいないなぁ、ってことで、それをさらにプログラムで実装してみる、ということをいくつかやってみようかと。

で、その一つが最小公倍数、最大公約数を求めること。

命題

$n$ 個の自然数の集合をAとする。 $（n \geqq 2$ ）

Aについて、最大公約数と最小公倍数を求めよ。

なお、Aの各要素の値は全て異なるものとする。

0ではない複数の整数の公倍数のうち最小の自然数をさす。

公倍数は「２つ以上の整数に共通な倍数」。

例えば、2,3の公倍数は-18,-12,-6,0,6,12,18などである。ただし、算数では、倍数に0を含めないので、公倍数にも0を含めない。

少なくとも1個が0ではない複数の整数の公約数のうち最大のものを指す。

公約数は「2つ以上の整数に共通な約数」。

例えば、 12と15の公約数は 12と15の最大公約数3を求め、最大公約数3の約数1,3となる。

実装の前に、そもそもどうやって求めてるんだっけ？を整理。

まずはAがこの場合。

$A \left\{ 6,15 \right\}$

各要素を素因数分解をして、素因数分解の結果の積集合(どっちにも含まれる)の積が最大公約数。

和集合(どちらかに含まれる。重複は除外)の積が最小公倍数として求められそう。

$6=2\times3$

$15=3\times5$

積集合(どっちにも含まれる)の3が最大公約数。

和集合(どちらかに含まれる)ものの積 $2\times3\times5 = 30$ が最小公倍数。

素因数分解の結果を一時的に保持する際に、素因数として登場する素数は同じものが並んでいた方が処理はしやすそう。

$6=2^{1}\times3^{1}\times5^{0}$

$15=2^{0}\times3^{1}\times5^{1}$

$n^{0}=1$ だし。