CodeIQ のアルゴリズム問題「チョコの量を減らせ！」by @hyuki に解答しました
CodeIQ のアルゴリズム問題（出題者：結城 浩 氏 @hyuki）に先日挑戦してきました。
挑戦者求む！【アルゴリズム】チョコの量を減らせ！ by The Essence of Programming 結城 浩│CodeIQ
昨日締切だったので、もう大丈夫ですよね？
私が解答に使ったプログラムを公開します。
解答（言語：Ruby）
Point
Point は言うまでもなく、78桁という文字通りの天文学的数字*1の素因数分解。
Ruby 標準の prime ライブラリの素因数分解に頼ってちゃ、たぶん一生かかっても終わりません。
私の解答は、見て分かるとおり、素因数分解を独自実装しています。
実装には、2つの乱択アルゴリズムを組み合わせて使用。
- ミラー-ラビン法（素数判定）(wikipedia:ミラー-ラビン素数判定法)
- ポラード・ロー素因数分解法（因数検出）(wikipedia:ポラード・ロー素因数分解法)
ま、独自実装と言っても Wikipedia に載っているアルゴリズムをほぼそのまま流用しただけなんですけどね。ミラー-ラビン法（以下「MR法」と略記）に関しては同じ Ruby なんでまるぱくりなのがばればれですね(^-^;
ただポラード・ロー法（以下「ρ法」と略記）に載っているアルゴリズムは、（素）因数を見つけ出すものだけなので、それを繰り返し利用してきちんと素因数分解を実装しています。
あとρ法の方は、Wikipedia にも記載があるとおり、素数だと検出に失敗するのですが、それがある程度大きな素数だと失敗という結果が出るまでに非常に時間がかかります*2。また素因数分解法と記述があるのですが、実際にはこれは「約数」を見付けるアルゴリズムであって、必ずしも「素因数」が検出されるわけではないんですよね*3。そちらに関しては Wikipedia には記載がないですけど。
だから、MR法を組み合わせたわけです。まずMR法で素数じゃないか判定する、素数じゃないと出たらρ法で約数を見つける、見付かった約数を再帰呼出で素因数分解する、また元の数を見付けた約数で割った数も再帰呼出で素因数分解する。基本的な流れはそんな感じです。
ということで、
404 Blog Not Found:Math - おまいら素因数分解どうしてますか?
みなさんは素因数分解の必要にせまられたとき、どうしてますか?
ないものは自分で作る！
これ基本！
