最大公約数 (paizaランク C 相当) 

素因数分解で最大公約数を求める

今回は素因数分解を用いた最大公約数を求める問題でした。最大公約数は、pythonの組み込み関数gcd()、ユークリッドの互除法でも求められますが、素因数分解を用いても最大公約数が求められます。

与えられる整数ごとに、素因数分解を行い、それぞれの因数が出てくる個数の最小値を求めることで、最大公約数が求められます。しかし、共通の素因数だけでなく、他の整数には含まれていない素因数の数を「0」個として形状しなければうまく答えが導けないので、全ての整数について素因数を求めた後に、各整数に含まれない素因数の個数を「0」として初期化しておくのに苦労しました。

辞書型で素因数と個数を格納する

筆者は、各整数の素因数と個数をそれぞれ辞書型に格納しておき、全ての整数の素因数と個数を求めた後に、keys()を使って一つのkeylistを辞書型で格納しました。そして改めて、各整数の答えの辞書にkeylistの中に含まれない素因数の個数を「0」として追加しておきます。

最小値の配列で素因数の個数の最小値を求める

ここまで準備できれば、後は全ての整数の素因数と個数の最小値を求めるだけですので、minanserという最小値だけを格納する配列を用意して、どれか一つの整数の素因数とこ数の答えで初期化し、残りの整数の答えの最小値を更新することで、求める最大公約数を算出することができるようになります。