tuneoの日記： 算数力を高める：３つかけるとnになる自然数の組を求める

任意の自然数nに対して、a * b * c = nを満足する自然数の組a, b, cを求める。例えばn = 8なら1, 2, 4とか2, 2, 2とか1, 1, 8とか（もっとあるけど）、n = 27なら3, 3, 3とか9, 1, 3とか1, 1, 27とかそんな具合。回転とか対称とかは考慮しないので、条件に該当する組み合わせは全部列挙できないといかん。

頭のクッソ悪いPythonコードは以下の通り。

for a in range(1, n + 1):
    for b in range(1, n + 1):
        for c in range(1, n + 1):
            if a * b * c == n:
                print("%d, %d, %d" % (a, b, c))

実際にはn = 256程度までを想定しており、総当たりで考えたとしても1677万通りもやればいいわけだ。さいきんのこうそくなぷろせっさをもってすれば何ほどのこともあるまいし、どうしても早くしたいなら問題を分割してマルチプロセスで高速化すればいいのだ！（←死ぬほど間違ったアプローチ）。……という冗談はさておき、高速化の種はいくつか思い付く。

1. ループを1～nまでのすべての自然数で総当たりにする必要はない（多くてもnのすべての約数について考えれば足りる）。
2. 内側のループは回数が減らせる。b <= n / a, c <= n / a / bは明らか。

というところで高速化してみればいいのかな。あいにく今日は自宅でパソコン2台使って実験をやるから忙しいのだ。ゲームとかもしなきゃいけないし（台無し）

というわけでメモ。

因数の組合せ

[route127 (38618)]

素因数のリストを3分割する組合せを計算すると効率良いのでは。
perlだと素因数分解 [cpan.org]、組合せ [cpan.org]、分割数 [cpan.org]とモジュール揃ってるので書いてみましたけど牛刀割鶏ですね。
pythonでもその辺のモジュールは探せばありそうですが。
#算数力あまりは高まらなさそう。

Re:因数の組合せ

[tuneo (2938)]

分割のパターンを求めて素因数のリストを分割し、部分リスト？の要素の積を求めて、とかやってると「重い」アルゴリズムになりそうです。

ちなみに以前やっつけで作った際は、nの約数のリストから3個選ぶ組み合わせを全部求めて、3個の積がnになるもの以外をハネるという雑な作りでしたw

必要最小限の修正

[taka2 (14791)]

一番内側のループは不要で、
n % (a * b) == 0 なら、c = n / (a * b) を出力、とするだけでいいかと。
オーダーがO(n^3) から O(n^2) への改善は非常に有効。

あとは、二つ目のループを b=n/aで回すぐらいですかね。

外側二つのループを、素因数分解したものにするのは、どちらにせよO(n^2)なので、
(それに素因数分解のコストが高い)ので、富豪的プログラミング的にはこのぐらいでやめとくかなぁ。

Re:必要最小限の修正

[tuneo (2938)]

コメントありがとうございます。
ご指摘のとおりn % (a * b) == 0ならc = n / (a * b)ですよねw