素因数分解のアルゴリズム 〜その1〜 - Mandy Code突然ですが、 問: 1〜100000までの数の中で最も約数の多いものを求めよ こんな問題がTwitterに流れていたらしく、定番っぽい問題ですが面白かったので数種類のやり方で解いてみます。 ある和nの約数の個数は、その数を素因数分解したときの指数だけを取り出してそれぞれに1足したものを掛けあわせれば求まります。 例えば12 = 2^2 * 3^1 なので、(2 + 1) * (1 + 1) = 6個となります。 つまり素因数分解が出来ればこの問題は解ける！ そこで初回は力技で素因数分解をしてみます。 まずコードをバーンと #!/usr/bin/env perl use strict; use warnings; main(); sub main { my $ans = +{ number => 0, factors => 0, result => +{}, }; for my $num (
