素因数の個数の平均 - inamori’s diaryProblem 468の計算量を見積もるときにこんな問題が思い浮かびました。 N以下を素因数分解したとき、素因数の個数の平均は？ 例えば、2、3、4 = 22、5なら1個、6 = 2 * 3なら2個とします。logNよりはずっと小さいと思われます。とりあえずコードを書いて調べてみましょう。 from itertools import * def div_pow(n, d): e = 0 while n % d == 0: e += 1 n /= d return e, n def make_factors_table(N): a = range(N + 1) for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n] == n)): for m in xrange(p, N + 1, p): if a[m] =
