1. 問題
 整数Nが2つ以上の異なる素数で割り切れるのであれば、最大素因数(LPD: Largest prime divisor)が存在する。NのLPDを探せ。Nの大きさは14桁以下。
 LPDが存在しなければ、出力を-1とする。

2. いくつかの例
 2は素数2でしか割り切れないので、そのLPDは存在しない。
 6は素数2, 3で割り切れるので、LPD=3。
 100は素数2, 5で割り切れるので、LPD=5。
 9は素数3でしか割り切れないので、そのLPDは存在しない。
 -385は素数5, 7, 11で割り切れるので、LPD=11。

3. 考え方
 与えられたNの大きさ。14桁もあるので、どう対処するかが大きな問題。
 結果的に言えたのは、この問題に限っては、一番単純な素因数分解法でやることだ。
 勿論、今回はたまたまうまく行っただけで、14桁の整数のLPDを高速に求めることは、そう簡単ではないはず。

4. 感想
 エラトステネスのふるいを利用しようとしたが、全然ダメだった。
 最終的に提出したプログラムの実行時間が0.090秒になったが、プログラムの内容に納得していない。
 なお、同じ入力値の計算を2度とやらないために、ハッシュテーブルを利用して、計算済の結果を保存しておいた。こちらも本来は要らないものかも。

Comments are closed.

Post Navigation